Complexity Theory Program
Workshop on Complexity Lower Bounds
February 22  27, 1998
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 BenDavid
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 AlgebroGeometric 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 readkTimes 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 kCNF 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 kProvability 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 Nonlinear Lower Bounds 
12:10  2:00
 Lunch Break 
2:00  2:40
 Noriko Arai: 
 Tractability of Cutfree 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) 