Refereed articles and articles in reviewed conference proceedings

• A Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives. LICS 06.

• Non-automatizability of bounded-depth Frege proofs. CCC 99 and Computational Complexity, 2004.

• A new proof of the weak pigeonhole principle. STOC 00 and Journal of Computer and Systems Science, 2002.

• Programs over semigroups of dot-depth one. Theoretical Computer Science, 2000.

• Circuit lower bounds collapse relativized complexity classes. CCC 99.

• Efficient threshold circuits for power series. Information and Computation, 1999.

• Threshold circuits of small majority-depth. Information and Computation, 1998.

• Towards lower bounds for bounded-depth Frege proofs with modular connectives. STOC 97 and Proof Complexity and Feasible Arithmetics, AMS, 1998.

• Upper and lower bounds for some depth-3 circuit classes. CCC 97 and Computational Complexity, 1997.

• Threshold circuits for iterated multiplication: using AC⁰ for free. STACS 93.

Technical reports

• Finding the widest empty corridor through a set of points. McGill University, 1988.

Ph.D. Thesis

• Threshold Circuits of Small Majority-Depth. McGill University, 1995.

Unpublished

• Introduction to Computer Science II: Notes for a course taught at Clarkson University. Latest version.

• Lecture notes on computational complexity, book in preparation. Latest version.