Computational Complexity

Friday, September 1, 2000 (All day) to Friday, June 1, 2001 (All day)

During the academic year 2000-2001, the School of Mathematics will host a special program on computational complexity theory at the Institute for Advanced Study. Several senior researchers will be in residence at the Institute for the year, and we expect a large number of junior visitors and post-doctorate fellows. Some topics on which special focus is planned are:

  • Boolean and Algebraic complexity -- ( towards P vs NP )
  • Proof complexity -- ( towards NP vs coNP )
  • Computational Randomness -- ( towards P vs BPP vs EXP )

The following organizers of the special program are as follows:

John Hastad, Royal Institute of Technology, Sweden.
Pavel Pudlak, The Czeck Academy of Sciences, Czeck Republic. (Fall Term Only.)
Ran Raz, The Weizmann Institute of Science, Israel.
Alexander Razborov, Steklov Mathematical Institute, Russia.
Avi Wigderson, Institute for Advanced Study

Members, visitors and students participating in the special program will be:

Mikhail Alekhnovitch
Eli Ben-Sasson
Nicola Galesi
Valentine Kabanets
Gil Kalai
Satyanarayana Lokam
Roy Meshulam
Omer Reingold
Alex Samorodnitsky
Ronen Shaltiel
Benny Sudakov
Salil Vadhan
Dieter van Melkebeek
Srinivasan Venkatesh
Catherine Yan

Workshops and Conferences:

Complexities of Proofs and Computations
December 10 - 16, 2000 at the Instititute for Advanced Study
Organizers: Avi Wigderson, Pavel Pudlak and Alexander Razborov.
Additional information on this workshop will be posted in September.

Invited participants are:

Mikos Atjai
Paul Beame
Maria Bonet
Samuel Buss
Stephen Cook
Christian Riis Flor
Russell Impagliazzo
Jan Krajicek
Toniann Pitassi
Steven Rudich
Jiri Sgall
Gaisi Takeuti
David Wood

Last updated May 31, 2000