Research Interests

Theory of computation, computational complexity, circuit complexity, proof complexity, algebraic theory of automata.

Grants

• 1996-2005: Fonds pour la Formation de Chercheurs et l'Aide à la Recherche (FCAR), Québec, Canada. Approche algébrique dans l'étude du parallélisme et de la complexitée du calcul. (Algebraic approach to the study of parallelism and computational complexity.) With M. Beaudry, F. Lemieux (99-05), P. McKenzie, J. Mullins (96-99) and D. Thérien. $360,000.

• 1999-2003: National Science Foundation (NSF), U.S.A. Grant CCR-9877150. Small-Depth Circuit Complexity and Relativized Computation. With R. Beigel. $278,155.

Publications