DIMACS Workshop on Intrinsic Complexity of Computation
April 10 - 13, 2000
DIMACS Center, Rutgers University, Piscataway, NJ
- Organizers:
- 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.