DIMACS 1999-2001 Special Year on Computational Intractability: Overview


The notion of computational intractability lies at the heart of computer science, and is central to the interface between discrete mathematics and theoretical computer science. Research on intractability has two long range goals:

1. To identify which computational problems are tractable and which are intractable.

2. To develop algorithmic strategies for dealing with problems which are intractable.

These two aims have been the subject of intense research efforts over the past twenty five years, and these efforts have been extremely fruitful with a wealth of fundamental results, both positive and negative results in areas such as approximation algorithms, circuit lower bounds, and the relationship between intractability and randomized computation. The time is ripe for a refocusing of efforts, in order (i) to consolidate and build on the substantial body of knowledge and techniques that have been developed in the past, and (ii) to identify the next set of research directions and subgoals that will move us towards the ultimate goals of the field.

It is our goal to involve a large number of people in the special year, in the usual DIMACS mode of bringing together people with different backgrounds and points of view. Computational intractability is of direct interest to a large number of researchers working in the theory of algorithms and complexity theory. The field of complexity lower bounds has been an area of interest to discrete mathematicians and logicians. Algorithm design and analysis fosters interactions between theoreticians, discrete mathematicians, probabilists, and researchers in applied areas who need to use algorithms for hard problems. The search for new mathematical approaches in both complexity theory and algorithms is causing the field to branch out to other areas of mathematics, e.g., algebraic geometry and topology, and we will encourage interactions with these and other fields.

Opportunities to participate:


Up. Index of Special Year on Computational Intractability
DIMACS Homepage
Contacting the Center
Document last modified on August 22, 2000.