Home Page for Alan Skelley

From November 2006 I am an NSERC postdoctoral fellow at the Computer Science department of the "La Sapienza" University in Rome, hosted by Nicola Galesi.

From September 2005 to October 2006 I was a visiting scholar in the Department of Mathematical Logic, Numerical Algebra and Graph Theory of the Mathematical Institute of the Academy of Sciences of the Czech Republic.

In September 2005 I completed my Ph.D. in the Computer Science department of the University of Toronto. My Ph.D. supervisor was Stephen A. Cook.
In 2000, I completed my M.Sc. under the supervision of Prof. Cook.

Here are my CV: [ps, pdf] and research statement:[ps, pdf]
A resume with a more industrial focus is here: [ps, pdf]

Contact Information

Alan Skelley
Dipartimento di Informatica
Università degli Studi di Roma "La Sapienza"
Via Salaria 113
00198 Roma
Italy
Home: +39 06 810-7889
Mobile: +39 334-194-5435
Permanent Email: alan@cs.toronto.edu

My "permanent" address in Canada:

Alan Skelley
P.O. Box 105
Madeira Park, BC V0N 2H0
Canada

Research

I am interested in many aspects of computational complexity and algorithms. My research concerns bounded arithmetic and propositional proof complexity.
Here are my research papers and writings:

A Resolution Lower Bound for a Principle Capturing the Hardness of Depth-1 LK [ps, pdf]
Alan Skelley and Neil Thapen
Submitted
NP Search Problems in Low Fragments of Bounded Arithmetic [ps, pdf]
Jan Krajicek, Alan Skelley and Neil Thapen
The Journal of Symbolic Logic, 72(2), pp. 649-672, 2007.
Third-Order Computation and Bounded Arithmetic [ps, pdf]
Alan Skelley
Appeared in the proceedings of the Second Conference on Computability in Europe (CiE 2006), University of Wales Swansea, Computer Science Report Series; full version invited to a special issue of the Journal of Logic and Computation
Ph.D. Dissertation
Theories and Proof Systems for PSPACE and the EXP-Time Hierarchy [ps, pdf]
(Final corrected Ph.D. dissertation)
Also available from the ECCC archive
Supervised by Stephen A. Cook
University of Toronto, 2005
A Third-Order Bounded Arithmetic Theory for PSPACE [ps, pdf, bibTeX]
Alan Skelley
Appeared in the proceedings of Computer Science Logic 2004, 18th International Workshop of the EACSL, Springer LNCS 3210, pp. 340-354.
Propositional PSPACE reasoning with Boolean Programs Versus Quantified Boolean Formulas [ps, pdf, bibTeX]
Alan Skelley
Appeared in the proceedings of ICALP 2004, 31st International Colloquium on Automata, Languages and Programming, Springer LNCS 3142, pp. 1163-1175.
M.Sc. Thesis
Relating the PSPACE Reasoning Power of Boolean Programs and Quantified Boolean Formulas [ps, pdf]
Also available from the ECCC archive
Supervised by Stephen A. Cook
University of Toronto, 2000.
DB2 Advisor: An Optimizer Smart Enough to Recommend Its Own Indexes [pdf, bibTeX]
Gary Valentin, Michael Zuliani, Danny Zilio, Guy Lohman, Alan Skelley
Appeared in the proceedings of ICDE 2000, 16th International Conference on Data Engineering.

Talks Given:

Interdepartmental Seminar on Algorithmics, University of Rome "La Sapienza", 2007
Logic Seminar at the Mathematical Institute of the Academy of Sciences of the Czech Republic, Prague, 2006.
Computability in Europe, Swansea, UK, 2006.
Prague-Vienna Workshop on Proof Theory and Proof Complexity, January 2006.
Indiana University Logic Seminar, November 2005.
Fall School of Logic of the Logic Seminar at the Mathematical Institute of the Academy of Sciences of the Czech Republic, September 2005.
CSL 2004, Karpacz, Poland.
ICALP 2004, Turku, Finland.
Banff International Research Station, workshop on advances in complexity, July 2004.
ICC 2003 (satellite workshop of LICS).
Fall School of Logic of the Logic Seminar at the Mathematical Institute of the Academy of Sciences of the Czech Republic, September 2001.
Institute for Advanced Study, workshop on proof complexity, December 2000.
University of Toronto, theory seminar, November 2000.

Refereeing

Unpublished Notes and Writings:

Some Results Concerning G1 and Polynomial Local Search [ps, pdf]
Alan Skelley
Gives a direct link between PLS and a witnessing problem for G1 proofs.
Subsystems of BPLK [ps, pdf]
Alan Skelley
Discusses weaker subsystems of BPLK.

Departmental Checkpoint Papers:

Theories and Proof Systems for PSPACE and the Exponential-Time Hierarchy [ps, pdf]
Thesis proposal paper
Revised Research Proposal or Preliminary Thesis Proposal [ps, pdf]
Some Open Problems in Bounded Arithmetic and Propositional Proof Complexity [ps, pdf]
Research proposal paper
Bounded Arithmetic vs. Propositional Proof Systems vs. Complexity Classes [ps, pdf]
Depth oral survey paper

This is version

$Id: index.html,v 1.24 2007/05/04 13:40:59 alan Exp $

of this document.