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)

A*daptive packet routing for bursty adversarial traffic*

January 23

Micah Adler (University of Toronto)

P*rotocols 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*