Publications
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
AC0 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.