https://www.dagstuhl.de/19121

17. – 22. März 2019, Dagstuhl-Seminar 19121

Computational Complexity of Discrete Problems

Organisatoren

Anna Gál (University of Texas – Austin, US)
Oded Regev (New York University, US)
Rahul Santhanam (University of Oxford, GB)
Till Tantau (Universität zu Lübeck, DE)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 9, Issue 3 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

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.

Summary text license
  Creative Commons BY 3.0 Unported license
  Anna Gál, Rahul Santhanam, and Till Tantau

Dagstuhl-Seminar Series

Classification

  • Data Structures / Algorithms / Complexity

Keywords

  • Computational complexity
  • Circuit complexity
  • Communication complexity
  • Randomness
  • Parametrisation

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.