TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 19121

Computational Complexity of Discrete Problems

( Mar 17 – Mar 22, 2019 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/19121

Organizers

Contact


Schedule

Motivation

Computational complexity studies the amount of resources (such as time, space, randomness, or communication) that are necessary to solve computational problems in various models of computation. Finding efficient algorithms for solving computational tasks is crucial for practical applications. Despite a long line of research, for many problems that arise in practice it is not known if they can be solved efficiently – in particular in polynomial time. Beside questions about the existence of polynomial time algorithms for problems like Satisfiability or Factoring, where the best known algorithms run in exponential time, there is a huge class of practical problems where algorithms with polynomial running time (e.g. cubic or even quadratic time) are known, but it would be important to establish whether these running times are best possible, to what extent they can be improved, and whether parallel algorithms allow improvements of the runtime.

These fundamental questions motivate developments in various areas from algorithm design to circuit complexity, communication complexity and coding theory. During this Dagstuhl Seminar, we plan to discuss some of the most exciting recent developments in those areas related to computational complexity.

The bulk of the seminar will be taken up by talks and discussions. The topics will depend on and be driven by the participants, who will share their current research interests in talks, open problem sessions, and smaller group research. The list of topics will include – but not be limited to – subjects such as formula size – especially new results on lower bounds –, complexity measures of Boolean functions, lower bounds for algorithm runtimes arising from connections to Satisfiability problems, the relationship of circuit complexity and fixed parameter tractability, communication complexity, as well as deep learning and circuit complexity.

The seminar is a continuation of the series of Dagstuhl Seminars entitled “Computational Complexity of Discrete Problems” and formerly “Complexity of Boolean Functions.” It will build on the long experience and focus on what has made the series strong in the past: bringing together the leading experts and the exceptionally talented junior researchers to discuss the most exciting recent developments in different areas of computational complexity of discrete problems – both regarding recent results, but also regarding open problems.

Copyright Anna Gál, Oded Regev, Rahul Santhanam, and Till Tantau

Summary

Computational complexity theory is the study of computation under bounded resources, and the tradeoffs thereof offered by specific problems and classes of problems in various computational models. Such resources include time and space for classical computation, randomnesss, non-determinism, and oracles for more advanced uniform machines, size/advice for circuits/non-uniform computation, interaction for communication protocols, length and depth for proof complexity, and much more. The goals of work in this field are not only to discover and improve these tradeoffs, but ideally to find tight lower bounds to match the solutions that have been found, and use such results in one of the models to inform results in the others. Despite decades of work on these problems, the answers to many foundational questions (such as P vs NP, P vs BPP, NP vs co-NP) still remain out of reach.

For the 2019 instalment of the seminar series Computational Complexity of Discrete Problems - which evolved out of the seminar series Complexity of Boolean Functions that dates back to the founding of Dagstuhl - Anna Gál, Oded Regev, Rahul Santhanam, and Till Tantau invited 40 participants to Dagstuhl to work towards discovering new results in the field. The seminar started with the assembly of a large "graph of interests" that allowed the participants both to present their own research interests and to see how these align with the other present researchers. The bulk of the research work was then done in the form of, on the one hand, talks in the morning and late afternoon and, on the other hand, break-out sessions and small discussions in the afternoon by smaller groups.

A distinguishing feature of the seminar talks were the lively discussions during and after the talk: given the often highly abstract and specialized topics presented by the experts in the field, lively discussions are by no means a given and they proved to be both rewarding and helpful for all participants. In the informal afternoon sessions, smaller groups of researchers had ample time to tackle the open problems of the field; with some discussions still going on after midnight. Two events - the traditional Wednesday hike and the traditional wine-and-cheese party on Thursday - allowed everyone well-earned breaks from doing research on computational complexity.

The range of topics covered by the participants during the seminar was broad and included derandomization, lower bounds for specific problems, communication complexity, complexity classes, graph algorithms, learning theory, coding theory, and proof complexity. Specific selected results presented throughout include:

  • A proof that the Log-Approximate-Rank Conjecture is false, yielding the first exponential gap between the logarithm of the approximate rank and randomized communication complexity for total functions.
  • An oracle separation of BQP and the polynomial hierarchy, showing a strong converse to the Bennett et al. oracle relative to which BQP cannot solve NP-complete problems in sub-exponential time.
  • Improved lower bounds for the Minimum Circuit Size Problem, including
    • MCSP not in AC^{0}[p],
    • MCSP requires N^{3-o(1)}-size de Morgan formulas,
    • MCSP requires N^{2-o(1)}-size general formulas,
    • MCSP requires smash{2^{Omega(N^{1/d+2.01})}}-size depth-d AC^{0} circuits,
    where the first result is achieved by showing MCSP can solve the coin problem and the others using properties of local pseudorandom generators.

Open problems were posed by Amit Chakrabarty, Alexander Golovnev, Or Meir, and Omri Weinstein.

The organizers, Anna Gál, Oded Regev, Rahul Santhanam, and Till Tantau, would like to thank all participants at this point for the many contributions they made, but we would also like to especially thank the Dagstuhl staff for doing -- as always -- an excellent job and helping with organizational matters and with making everyone feel welcome.

Copyright Anna Gál, Rahul Santhanam, and Till Tantau

Participants
  • Eric Allender (Rutgers University - Piscataway, US) [dblp]
  • Paul Beame (University of Washington - Seattle, US) [dblp]
  • Harry Buhrman (CWI - Amsterdam, NL) [dblp]
  • Igor Carboni Oliveira (University of Oxford, GB) [dblp]
  • Katrin Casel (Hasso-Plattner-Institut - Potsdam, DE) [dblp]
  • Amit Chakrabarti (Dartmouth College - Hanover, US) [dblp]
  • Sourav Chakraborty (Indian Statistical Institute - Kolkata, IN) [dblp]
  • Arkadev Chattopadhyay (TIFR - Mumbai, IN) [dblp]
  • Gil Cohen (Princeton University, US) [dblp]
  • Anindya De (University of Pennsylvania - Philadelphia, US) [dblp]
  • Lukáš Folwarczný (Charles University - Prague, CZ) [dblp]
  • Lance Fortnow (Georgia Institute of Technology - Atlanta, US) [dblp]
  • Anna Gál (University of Texas - Austin, US) [dblp]
  • Alexander Golovnev (Harvard University - Cambridge, US) [dblp]
  • Kristoffer Arnsfelt Hansen (Aarhus University, DK) [dblp]
  • Prahladh Harsha (TIFR - Mumbai, IN) [dblp]
  • Johan Hastad (KTH Royal Institute of Technology, SE) [dblp]
  • Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
  • Michael Kapralov (EPFL - Lausanne, CH) [dblp]
  • Mathew Katzman (University of Oxford, GB)
  • Antonina Kolokolova (Memorial University of Newfoundland - St. John's, CA) [dblp]
  • Swastik Kopparty (Rutgers University - Piscataway, US) [dblp]
  • Michal Koucký (Charles University - Prague, CZ) [dblp]
  • Matthias Krause (Universität Mannheim, DE) [dblp]
  • Meena Mahajan (Institute of Mathematical Sciences - Chennai, IN) [dblp]
  • Or Meir (University of Haifa, IL) [dblp]
  • Jakob Nordström (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
  • Ramamohan Paturi (University of California - San Diego, US) [dblp]
  • Pavel Pudlák (The Czech Academy of Sciences - Prague, CZ) [dblp]
  • Rüdiger Reischuk (Universität zu Lübeck, DE) [dblp]
  • Michael E. Saks (Rutgers University - Piscataway, US) [dblp]
  • Rahul Santhanam (University of Oxford, GB) [dblp]
  • Ronen Shaltiel (University of Haifa, IL) [dblp]
  • Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
  • Avishay Tal (Stanford University, US) [dblp]
  • Till Tantau (Universität zu Lübeck, DE) [dblp]
  • Thomas Thierauf (Hochschule Aalen, DE) [dblp]
  • Jacobo Torán (Universität Ulm, DE) [dblp]
  • Ben Lee Volk (Caltech - Pasadena, US) [dblp]
  • Omri Weinstein (Columbia University - New York, US) [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 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 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
  • circuit complexity
  • communication complexity
  • randomness
  • parametrisation