Computational Complexity of Discrete Problems

Summary

Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify natural families of Boolean relations according to fundamental complexity measures like time and space, both in the uniform and in the nonuniform setting. Several models of computation have been developed in order to capture the various capabilities of digital computing devices, including parallelism, randomness, and quantum interference.

In addition, complexity theorists have studied other computational processes arising in diverse areas of computer science, each with their own relevant complexity measures. Several of those investigations have evolved into substantial research areas, including:

In addition, complexity theorists have studied other computational processes arising in diverse areas of computer science, each with their own relevant complexity measures. Several of those investigations have evolved into substantial research areas in their own right, including:

• proof complexity, interactive proofs, and probabilistically checkable proofs (motivated by verification),
• approximability (motivated by optimization),
• pseudo-randomness and zero-knowledge (motivated by cryptography and security),
• computational learning theory (motivated by artificial intelligence),
• communication complexity (motivated by distributed computing), and
• query complexity (motivated by databases).

The analysis and relative power of the basic models of computation remains a major challenge, with intricate connections to all of the areas mentioned above. Several lower bound techniques for explicitly defined functions form the basis for results in propositional proof complexity. The structure that underlies the lower bounds has led to efficient sample-based algorithms for learning unknown functions from certain complexity classes. Close connections have been discovered between circuit lower bounds for certain uniform complexity classes and the possibility of efficient derandomization. The discovery of probabilistically checkable proofs for NP has revived the area of approximability and culminated in surprisingly tight hardness of approximation results for a plethora of NP-hard optimization problems.

Thus, new results that relate or separate different models of computation and new methods for obtaining lower and upper bounds on the complexity of explicit discrete problems are topics of general importance for the computer science community.

The seminar "Computational Complexity of Discrete Problems" has evolved out of the series of seminars entitled "Complexity of Boolean Functions," a topic that has been covered at Dagstuhl on a regular basis since the foundation of IBFI. Over the years, the focus on nonuniform models has broadened to include uniform ones as well. The change in title reflects and solidifies this trend.