Workshop on Complexity Lower Bounds
February 22 - 27, 1998, The Fields Institute
Description
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.
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
Schedule
| 09:30 to 10:30 |
Geometric Complexity I: An Algebro-Geometric Approach to Computational Complexity
Ketan Mulmuley, University of Chicago Location:The Fields Institute |
| 10:30 to 11:00 |
Break
|
| 11:00 to 12:00 |
Randomized Complexity Lower Bounds
Dima Grigoriev, Penn State University Location:The Fields Institute |
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 15:00 |
Lower Bounds on Randomized Branching Programs
Marek Karpinski, University of Bonn Location:The Fields Institute |
| 15:00 to 15:30 |
Break
|
| 15:30 to 16:00 |
On Separating the read-k-Times Branching Programs Hierarchy
Jayram Thathachar, University of Washington Location:The Fields Institute |
| 16:20 to 17:30 |
Lecture I of Coxeter Series
Alexander A. Razborov, Steklov Mathematical Institute Location:The Fields Institute |
| 09:30 to 10:30 |
A Gap Theorem for Derandomization
Avi Wigderson, Hebrew University Location:The Fields Institute |
| 10:30 to 11:00 |
Break
|
| 11:00 to 12:00 |
On the Complexity of Satisfiability of Random k-CNF Formulas
Paul Beame, University of Washington Location:The Fields Institute |
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 15:00 |
Geometric Complexity II
Ketan Mulmuley University of Chicago Location:The Fields Institute |
| 15:00 to 15:30 |
Break
|
| 16:00 to 17:00 |
On the Hardness of k-Provability and Automatizability of Proof Systems
Toni Pitassi, University of Arizona Location:The Fields Institute |
| 10:00 to 10:20 |
Coffee
|
| 10:20 to 11:20 |
Seperation of the Monotone NC Hierachy
Ran Raz, Weizmann Institute of Science Location:The Fields Institute |
| 11:30 to 12:10 |
Polynomial vicinity Circuits and Non-linear Lower Bounds
Ken Regan, State University of New York at Buffalo Location:The Fields Institute |
| 12:10 to 14:10 |
Lunch
|
| 14:00 to 14:40 |
Tractability of Cut-free Gentzen Type Propositional Calculus
Noriko Arai, Hiroshima City University Location:The Fields Institute |
| 15:10 to 16:30 |
Break
|
| 16:30 to 17:40 |
Lecture II of Coxeter Series
Alexander A. Razborov, Steklov Mathematical Institute Location:Galbraith Building, Room 220 |
| 09:30 to 10:20 |
Lower Bounds for Monotone Span Programs
Anna Gal, University of Texas at Austin Location:The Fields Institute |
| 10:20 to 10:50 |
Break
|
| 10:50 to 11:40 |
Complexity Gaps for Nullstellansatz Proofs
Soren Moller Riis, University of �rhus Location:The Fields Institute |
| 12:00 to 14:00 |
Lunch
|
| 14:00 |
Skating Part at Harbourfront Centre
Location:Harbourfront Centre |
| 09:30 to 10:30 |
Problem Sessions and Talks
Location:The Fields Institute |
| 10:30 to 11:00 |
Break
|
| 12:00 to 14:00 |
Lunch
|
| 14:00 to 15:00 |
Problem Sessions
Location:The Fields Institute |
| 16:20 to 17:30 |
Lecture III of Coxeter Series
Alexander A. Razborov, Steklov Mathematical Institute Location:The Fields Institute |
