DIMACS Workshop on Intrinsic Complexity of Computation

April 10 - 13, 2000
DIMACS Center, Rutgers University, Piscataway, NJ

Paul Beame, University of Washington, beame@cs.washington.edu
Steven Rudich, Carnegie Mellon University, rudich+@cs.cmu.edu
Andrew Yao, Princeton University, yao@cs.princeton.edu
Presented under the auspices of the Special Year on Computational Intractability.

Computational Complexity Theory is the study of how much of a given resource (such as time, space, parallelism, randomness, algebraic operations, communication, quantum steps, or proof length) is required to perform the computations that interest us the most. Four decades of fruitful research have produced a rich and subtle theory of the relationship between different resource measures and problems. At the core of the theory are some of the most alluring open problems in mathematics.

This workshop will be an ideal forum to review our progress in and prospects for proving lower bounds on the complexity of natural computational problems. To this end, we have arranged for a distinguished list of plenary speakers to share their historical, philosophical, and technical perspectives:

Miki Ajtai, IBM Almaden
Lance Fortnow, NEC, Princeton
Russell Impagliazzo, UCSD, San Diego CA
Steven Rudich, Carnegie-Mellon University
Avi Wigderson, Institute For Advanced Study, Princeton and Hebrew University
Andrew Yao, Princeton University

In addition to the plenary talks, the workshop will include participant talks on current research.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on March 22, 2000.