DIMACS Workshop on Intrinsic Complexity of Computation
April 10 - 13, 2000
DIMACS Center, Rutgers University, Piscataway, NJ
Presented under the auspices of the Special Year on Computational Intractability.
- Paul Beame, University of Washington, firstname.lastname@example.org
- Steven Rudich, Carnegie Mellon University, email@example.com
- Andrew Yao, Princeton University, firstname.lastname@example.org
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
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
Contacting the Center
Document last modified on March 22, 2000.