The central and most challenging mathematical problems in complexity theory involve proving lower bounds on the complexity of specific problems. This workshop will bring together prominent researchers specialising in different aspects of the area, including combinatorial, logical, and algebraic lower bounds. Specific topics will include lower bounds for circuits, branching programs, propositional proofs, separation results for complexity classes, and proof limitations such as natural proofs.

Organizing Committee:

A. Borodin and S. Cook University of Toronto

Invited Speakers and Participants:

Micah Adler University of Toronto
Jeremy Avigad Carnegie Mellon University
Noriko Arai Hiroshima City University
Toshiyasu Arai Hiroshima University
Paul Beame University of Washington
Shai Ben-David Israel Institute of Technology
Maria Bonet Polytechnic University of Catalunya
Peter Clote Boston College
Jeff Edmonds York University
Lance Fortnow Centrum voor Wiskunde en Informatica
Anna Gal University of Texas at Austin
Dima Grigoriev Penn State University
Anna Gringauze Israel Institute of Technology
Armin Haken University of Toronto
Russell Impagliazzo University of California, San Diego
Bruce Kapron University of Victoria
Marek Karpinski University of Bonn
Valerie King University of Victoria
Jan Krajítk Mathematical Institute, Oxford
Satya Lokam Loyola University
Pierre McKenzie Université de Montréal
Ketan Mulmuley University of Chicago
Nicholas Pippenger University of British Columbia
Toni Pitassi University of Arizona
Pavel Pudlak Academy of Sciences of Czech Republic
Ran Raz Weizmann Institute of Science
Alexander A. Razborov Steklov Mathematical Institute
Ken Regan State University of New York at Buffalo
Soren Moller Riis University of Århus
Adi Rosen University of Toronto
Steven Rudich Carnegie Mellon University
Michael Saks University of Washington
Nathan Segerlind Carnegie Mellon University
Madhu Sudan Massachusetts Institute of Technology
Jayram Thathachar University of Washington
Denis Therien McGill University
Alasdair Urquhart University of Toronto
Avi Wigderson Hebrew University
Andrew Yao Princeton University

Professor Alexander A. Razborov of the Steklov Mathematical Institute will deliver lectures on February 23, 25, and 27 as part of the Fields Institute Coxeter Lecture Series.

Schedule

MONDAY, February 23
9:30 - 10:30 Ketan Mulmuley:
Geometric Complexity I: An Algebro-Geometric Approach
to Computational Complexity

10:30 - 11:00 Break
11:00 - 12:00 Dima Grigoriev:
Randomized Complexity Lower Bounds
12:00 - 2:00 Lunch Break
2:00 - 3:00 Marek Karpinski:
Lower Bounds on Randomized Branching Programs
3:00 - 3:30 Break
3:30 - 4:00 Jayram Thathachar:
On Separating the read-k-Times Branching Programs Hierarchy
4:20 - 5:30 A. A. Razborov:(Lecture I of Coxeter Series)

TUESDAY, February 24
9:30 - 10:30 Avi Wigderson:
A Gap Theorem for Derandomization

10:30 - 11:10 Break
11:10 - 12:00 Paul Beame:
On the Complexity of Satisfiability of Random k-CNF Formulas
12:00 - 2:00 Lunch Break
2:00 - 3:00 Ketan Mulmuley:
Geometric Complexity II
3:00 - 4:00 Break
4:00 - 4:50 Toni Pitassi:
On the Hardness of k-Provability and Automatizability of Proof Systems

WEDNESDAY, February 25
10:00 - 10:20 Coffee
10:20 - 11:20 Ran Raz:
Seperation of the Monotone NC Hierachy
11:30 - 12:10 Ken Regan:
Polynomial vicinity Circuits and Non-linear Lower Bounds
12:10 - 2:00 Lunch Break
2:00 - 2:40 Noriko Arai:
Tractability of Cut-free Gentzen Type Propositional Calculus
3:10 - 4:30 Break
4:30 - 5:30 A. A. Razborov (Lecture II of Coxeter Series)
NOTE: held in Room 220, Galbraith Building

THURSDAY, February 26
9:30 - 10:20 Anna Gal:
Lower Bounds for Monotone Span Programs
10:20 - 10:50 Break
10:50 - 11:40 Soren Riis:
Complexity Gaps for Nullstellansatz Proofs
12:00 - 2:00 Lunch Break
AFTERNOON: Skating Part at Harbourfront Centre

FRIDAY, February 27
MORNING: Problem Sessions and Talks
10:30 - 11:00 Break
12:00 - 2:00 Lunch Break
AFTERNOON: Problem Sessions
3:00 - 3:30 Break
4:20 - 5:20 A. A. Razborov (Lecture III of Coxeter Series)