Dagstuhl Seminar 08381
Computational Complexity of Discrete Problems
( Sep 14 – Sep 19, 2008 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/08381
Organizers
- Peter Bro Miltersen (Aarhus University, DK)
- Rüdiger Reischuk (Universität Lübeck, DE)
- Georg Schnitger (Universität Frankfurt, DE)
- Dieter van Melkebeek (University of Wisconsin - Madison, US)
Contact
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.
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Eli Ben-Sasson (Technion - Haifa, IL) [dblp]
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Beate Bollig (TU Dortmund, DE) [dblp]
- Mark Braverman (Microsoft New England R&D Center - Cambridge, US) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
- Lance Fortnow (Northwestern University - Evanston, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Martin Grohe (HU Berlin, DE) [dblp]
- Venkatesan Guruswami (Carnegie Mellon University, US) [dblp]
- Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
- Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
- Thomas Holenstein (Microsoft Corp. - Mountain View, US)
- Stasys Jukna (Universität Frankfurt, DE) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Michal Koucký (Czech Academy of Sciences - Prague, CZ) [dblp]
- Matthias Krause (Universität Mannheim, DE) [dblp]
- Miroslaw Kutylowski (Wroclaw University of Technology, PL)
- Troy Lee (Rutgers University - Piscataway, US) [dblp]
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- Jakob Nordström (MIT - Cambridge, US) [dblp]
- Pavel Pudlák (Czech Academy of Sciences, CZ) [dblp]
- Jaikumar Radhakrishnan (TIFR Mumbai, IN) [dblp]
- Oded Regev (Tel Aviv University, IL) [dblp]
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- Georg Schnitger (Universität Frankfurt, DE)
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Ronen Shaltiel (University of Haifa, IL) [dblp]
- Alexander Sherstov (University of Texas - Austin, US) [dblp]
- Amir Shpilka (Technion - Haifa, IL) [dblp]
- Hans Ulrich Simon (Ruhr-Universität Bochum, DE) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Till Tantau (Universität Lübeck, DE) [dblp]
- Denis Therien (McGill University - Montreal, CA) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (CalTech - Pasadena, US) [dblp]
- Dieter van Melkebeek (University of Wisconsin - Madison, US) [dblp]
- Stephan Waack (Universität Göttingen, DE)
- Philipp Woelfel (University of Calgary, CA) [dblp]
Related Seminars
- Dagstuhl Seminar 9235: Complexity and Realization of Boolean Functions (1992-08-24 - 1992-08-28) (Details)
- Dagstuhl Seminar 9711: Complexity of Boolean Functions (1997-03-10 - 1997-03-14) (Details)
- Dagstuhl Seminar 99441: Complexity of Boolean Functions (1999-10-31 - 1999-11-05) (Details)
- Dagstuhl Seminar 02121: Complexity of Boolean Functions (2002-03-17 - 2002-03-22) (Details)
- Dagstuhl Seminar 04141: Complexity of Boolean Functions (2004-03-28 - 2004-04-02) (Details)
- Dagstuhl Seminar 06111: Complexity of Boolean Functions (2006-03-12 - 2006-03-17) (Details)
- Dagstuhl Seminar 11121: Computational Complexity of Discrete Problems (2011-03-20 - 2011-03-25) (Details)
- Dagstuhl Seminar 14121: Computational Complexity of Discrete Problems (2014-03-16 - 2014-03-21) (Details)
- Dagstuhl Seminar 17121: Computational Complexity of Discrete Problems (2017-03-19 - 2017-03-24) (Details)
- Dagstuhl Seminar 19121: Computational Complexity of Discrete Problems (2019-03-17 - 2019-03-22) (Details)
- Dagstuhl Seminar 21121: Computational Complexity of Discrete Problems (2021-03-21 - 2021-03-26) (Details)
- Dagstuhl Seminar 23111: Computational Complexity of Discrete Problems (2023-03-12 - 2023-03-17) (Details)
- Dagstuhl Seminar 25111: Computational Complexity of Discrete Problems (2025-03-09 - 2025-03-14) (Details)
