Computational Complexity of Discrete Problems

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.