May 28, 2018

Complexity Theory Program

January to June 1998

Lectures by Alexander A. Razborov (Steklov Mathematical Institute)
February 23, 25 and 27, 1998

The discipline of Computer Science is a blend of mathematical theory and engineering oriented concepts. At the core of the science of computing is complexity theory, one of the (relatively) more established areas in a very young field. Briefly stated, the goal of complexity theory is to provide an "intrinsic" (i.e. as machine independent as possible) framework for studying the complexity of problems and the relation between various models and measures of complexity.
In one sense, the theory has been very successful in the identification of natural and invariant complexity classes and in identifying the fundamental issues. On the other hand, we have been largely unsuccessful to date in efforts to prove that particular computational problems are difficult to solve. But the field continues to progress and one sign of this progress is the number of related topics that have emerged. For example, modern cryptography is strongly based on complexity theoretic assumptions and concepts, and interactive proofs have led to new insights into approximation algorithms.

Organizing Committee

P. Beame (University of Washington)
A. Borodin (University of Toronto)
S. Cook (University of Toronto)
F. Fich (University of Toronto)
N. Pippenger (University of British Columbia)
C. Rackoff (University of Toronto)
A. Wigderson (Hebrew University)


February 23 - 27, 1998
Complexity Lower Bounds
Organizers: A. Borodin, S. Cook

May 10-15, 1998
Interactive Proofs, PCP's and Fundamentals of Cryptography
Organizers: S. Golwasser (MIT), C. Rackoff
Tentative Participants:
M. Bellare, R. Canetti, U. Feige, J. Feigenbaum, O. Goldreich, S. Goldwasser, J. Hastad, L. Levin, M. Luby, M. Naor, R. Ostrovsky, C. Papadimitriou, M. Sudan, A. Wigderson

June 1-5, 1998
Complexity Issues in Distributed and Parallel Computation
Organizer: F. Fich

Tentative Participants:
T. Chandra, M. Dietzfelbinger, V. Hadzilacos, M. Herlihy, P. Jayanti, E. Kranakis, D. Krizanc, T. Leighton, N. Lynch, P. MacKenzie, B. Maggs, F. Meyer auf der Heide, N. Nishimura, N. Pippenger, P. Ragde, V. Ramachandran, R. Reischuk, N. Santoro, N. Shavit, S. Toueg, E. Upfal

GRADUATE COURSES -- January - April, 1998


January 16
Adi Rosen (University of Toronto)
Adaptive packet routing for bursty adversarial traffic

January 23
Micah Adler (University of Toronto)
Protocols for asymmetric communcation channels

January 30
Dieter van Melkebeek (University of Chicago)
The sparse hard set problem for P

February 6
Anna Gal (University of Texas at Austin)
On arithmetic branching programs

February 20
Noriko H. Arai (Hiroshima City University)
A proper hierarchy of LK

March 5
John Watrous (University of Wisconsin at Madison)
Space-bounded quantum complexity