WORKSHOPS
SEMINARS
COXETER LECTURES-
Lectures by Alexander A. Razborov (Steklov Mathematical Institute)
February 23, 25 and 27, 1998
Overview
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)
WORKSHOPS
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
COMPLEXITY THEORY SEMINARS Winter 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
