Dagstuhl Seminar 11121
Computational Complexity of Discrete Problems
( Mar 20 – Mar 25, 2011 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/11121
Organizers
- Martin Grohe (HU Berlin, DE)
- Michal Koucký (Czech Academy of Sciences - Prague, CZ)
- Rüdiger Reischuk (Universität Lübeck, DE)
- Dieter van Melkebeek (University of Wisconsin - Madison, US)
Contact
- Andreas Dolzmann (for scientific matters)
- Andreas Dolzmann (for administrative matters)
Schedule
Computational models like Turing machines and Boolean circuits work on discrete input data. Even quantum computation and communication studied in the recent past are mainly applied to solve discrete problems. Analysing the computational complexity of such problems with respect to these models is one of the central topics in the theory of computation. Researchers try to classify algorithmic problems according to complexity measures like time and space -- both in the uniform and in the nonuniform setting. A variety of specialized computational models have been developed in order to better measure the complexity of certain classes of discrete problems.
Randomness has turned out to be another fundamental measure and added a lot of new intricate questions. Performing probabilistic choices within an algorithm one can design solution strategies for a given computational problem for which there are no obvious deterministic ones. Recently, large effort has been taken to remove randomness from probabilistic algorithms, so called derandomization. Here one tries to develop general techniques that can be applied to a wide range of discrete problems.
Information transfer is investigated according to the amount of communication necessary in different scenarios like 1-way channels or a bounded number of communication rounds. This is a basis for the design of efficient communication protocols. Furthermore, it has been observed that often ordinary computational problems given to a specific computational device can formally be analysed elegantly by concentrating on information flow aspects.
In addition, other computational processes arising in diverse areas of computer science have been studied, each with their own relevant complexity measures. Several of those investigations have evolved into substantial research areas, including:
- approximability (motivated by optimization),
- computational learning theory (motivated by artificial intelligence),
- query complexity (motivated by databases).
The analysis and relative power of basic models of computation remains a major challenge. New lower bound techniques for explicitly defined functions have brought the field a major step forward. For example, close connections have been discovered between circuit lower bounds for certain uniform complexity classes and the existence of pseudorandom generators and the possibility of efficient derandomization.
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 this research center. Over the years, the focus on nonuniform models has broadened to include uniform ones as well.
A salient feature of the current research in computational complexity is the interpenetration of ideas from different subareas of computational complexity and from other fields in computer science and mathematics. By organizing a generic seminar on computational complexity we have aimed to attract researchers from those various subareas and foster further fruitful interactions.
Investigating the complexity of discrete problems is one of the fundamental tasks in the theory of computation. On the one hand, new algorithmic techniques and new ways to look at a problem have led to better algorithms and protocols. On the other hand, typically more demanding is the task to prove lower bounds on the computational complexity of a concrete problem. Progress is still continuing, as seen for example in testing, derandomization and explicit constructions of combinatorial objects like extractors, that improves our knowledge considerably. Despite these significant steps forward that have been achieved in several subareas since our previous meeting three years ago, the general feeling among the participants was that we still have to work hard for many more years to get a good understanding what are the limits of efficient computation.
We like to thank the staff at Dagstuhl who -- as usual -- provided a marvellous surrounding to make this a successful meeting with ample space for undisturbed interactions between the participants.
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Matthew Anderson (University of Wisconsin - Madison, US) [dblp]
- Paul Beame (University of Washington - Seattle, US) [dblp]
- Eli Ben-Sasson (Technion - Haifa, IL) [dblp]
- Markus Bläser (Universität des Saarlandes, DE) [dblp]
- Andrej Bogdanov (The Chinese University of Hong Kong, HK) [dblp]
- Beate Bollig (TU Dortmund, DE) [dblp]
- Holger Dell (University of Wisconsin - Madison, US) [dblp]
- Martin Dietzfelbinger (TU Ilmenau, DE) [dblp]
- Andrew Drucker (MIT - Cambridge, US) [dblp]
- Michael Elberfeld (Universität Lübeck, DE) [dblp]
- Eldar Fischer (Technion - Haifa, IL)
- Lance Fortnow (Georgia Institute of Technology - Atlanta, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Martin Grohe (HU Berlin, DE) [dblp]
- Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
- Prahladh Harsha (TIFR Mumbai, IN) [dblp]
- Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
- Stasys Jukna (Goethe-Universität - Frankfurt a. M., 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]
- Troy Lee (National University of Singapore, SG) [dblp]
- Xin Li (University of Texas - Austin, US)
- Meena Mahajan (The Institute of Mathematical Sciences, IN) [dblp]
- Pierre McKenzie (University of Montréal, CA) [dblp]
- Or Meir (Stanford University, US) [dblp]
- Peter Bro Miltersen (Aarhus University, DK) [dblp]
- Robin A. Moser (ETH Zürich, CH) [dblp]
- Ilan Newman (University of Haifa, IL) [dblp]
- Jakob Nordström (KTH Royal Institute of Technology, SE) [dblp]
- Pavel Pudlák (Czech Academy of Sciences - Prague, CZ) [dblp]
- Oded Regev (New York University, US) [dblp]
- Rüdiger Reischuk (Universität Lübeck, DE) [dblp]
- Rahul Santhanam (University of Edinburgh, GB) [dblp]
- Georg Schnitger (Goethe-Universität - Frankfurt a. M., DE)
- Uwe Schöning (Universität Ulm, DE) [dblp]
- Nicole Schweikardt (Goethe-Universität - Frankfurt a. M., DE) [dblp]
- Srikanth Srinivasan (Rutgers University - New Brunswick, US) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Till Tantau (Universität Lübeck, DE) [dblp]
- Dieter van Melkebeek (University of Wisconsin - Madison, US) [dblp]
- Emanuele Viola (Northeastern University - Boston, US) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Fabian Wagner (Universität Ulm, DE)
- Thomas W. Watson (University of California - Berkeley, US) [dblp]
- 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 08381: Computational Complexity of Discrete Problems (2008-09-14 - 2008-09-19) (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)
Classification
- data structures / algorithms / complexity
Keywords
- computational complexity
- discrete problems
- Turing machines
- circuits
