Dagstuhl Seminar 25111
Computational Complexity of Discrete Problems
( Mar 09 – Mar 14, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25111
Organizers
- Swastik Kopparty (University of Toronto, CA)
- Meena Mahajan (The Institute of Mathematical Sciences & HBNI - Chennai, IN)
- Rahul Santhanam (University of Oxford, GB)
- Till Tantau (Universität zu Lübeck, DE)
Contact
- Andreas Dolzmann (for scientific matters)
- Simone Schilke (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
Overview
Computational complexity studies the amount of resources (such as time, space, randomness, communication, or parallelism) necessary to solve discrete problems – a crucial task both in theoretical and practical applications. Despite a long line of research, for many practical problems it is not known if they can be solved efficiently. Here, “efficiently” can refer to polynomial-time algorithms, whose existence is not known for problems like Satisfiability or Factoring. For the large data sets arising for instance in machine learning, already cubic or even quadratic time may be too large, but may be unavoidable as research on fine-grained complexity indicates. The ongoing research on such fundamental problems has a recurring theme: the difficulty of proving lower bounds. Indeed, many of the great open problems of theoretical computer science are, in essence, open lower bound problems.
This Dagstuhl Seminar, the 14th in a long-standing series of seminars on this theme, addressed several of these questions in the context of circuit and formula sizes, meta-complexity, proof complexity, fine-grained complexity, communication complexity, and classical computational complexity. In each area, powerful tools for proving lower and upper bounds are known, but particularly interesting and powerful results often arise from establishing connections between the fields. The seminar aimed to bring together a diverse group of leading experts and promising young researchers in these areas, to discuss and to discover new, further connections.
Technical Talks
The Dagstuhl Seminar saw thirty technical lengths, of durations ranging from 10 to 50 minutes, covering and going beyond the themes discussed above. While detailed talk abstracts appear later in this report, here is a brief topic-wise overview.
Hardness of Approximation and Local Testing
When faced with a computational problem for which an efficient solution is hard to find (e.g. if the problem is NP hard), we can hope to efficiently find approximate solutions. Hardness of approximation is the study of computational limitations to what kinds of approximation can be achieved efficiently, and it has been a flourishing subfield of theoretical computer science. A key ingredient for hardness of approximation theorems are probabilistically checkable proofs and local testing: where one wants to check properties of some large object while only querying a small randomly chosen part of it. Yuval Filmus presented a new unified approach to local testing of polymorphisms, generalizing linearity testing and monomial testing, previously proved using quite different techniques. Prahladh Harsha presented an optimal analysis of the classical “lines vs points” low degree test, which can detect when a given function has even just 1%-fraction agreement with a low-degree multivariate polynomial. Such local tests are central ingredients in state-of-the-art probabilistically checkable proofs and hardness of approximation results. Amey Bhangale described a long series of works that are part of a program to classify the hardness of approximating constraint satisfiable problems that are promised to be satisfiable. Shuichi Hirahara presented new results on average-case hardness of approximation for matrix multiplication, a topic that has seen much interest in recent years. The key ingredient here is a new proof of the classical Yao XOR lemma, a hardness amplification result with origins in cryptography. Sasha Golovnev gave a talk on barriers to proving exponential time complexity hardness (known as “SETH-hardness”) for many classical problems with unknown complexity like Hamiltonian cycles. Radu Curticapean gave a survey of a recent line of work on hardness of finding subgraphs. This line of work can now determine for every graph H the fine-grained complexity of finding copies of H in a given input graph; remarkably, the hardness results match classical algorithms based on dynamic programming and treewidth.
Meta-Complexity
Meta-complexity studies relationships between lower bounds, learning, pseudorandomness, cryptography and proofs, based on analysing the complexity of compression problems. Valentine Kabanets discussed how a central question in cryptography, namely whether witness encryption exists for NP, is equivalent to a central question in learning theory, namely whether computational learning is hard for NP. Zhenjian Lu defined the Heavy Avoid problem, which asks whether "heavy" elements for a samplable distribution, can be identified efficiently, and showed that this problem is closely related to uniform probabilistic lower bounds. Oliver Korten described connections between the Range Avoidance problem for NC0 circuits and previously well-studied problems about cell-probe lower bounds and NC0 pseudo-random generators. In each of these cases, the meta-complexity perspective leads to the identification of new connections and approaches.
Space-bounded Computation
Space-bounded computation was another important theme of the seminar; recent advances in catalytic computation have generated much excitement. Ian Mertz discussed the recent breakthrough result of Ryan Williams showing that time can be simulated in nearly squareroot space. Michal Koucký described a range of collapses of catalytic classes, including the results that catalytic non-deterministic space and catalytic randomized space are equivalent to catalytic deterministic space. Roei Tell presented work on the long-standing open question of whether randomized logarithmic space can be derandomized, showing that for two standard algorithmic tasks, namely solving connectivity and computing random walk probabilities for graphs, at least one is solvable more efficiently than was hitherto known. Amit Chakrabarti and Sumegha Garg discussed various models of streaming algorithms, which are special kinds of space-bounded algorithms analyzed using various information complexity techniques.
Query and Communication
Kaave Hosseini gave a sweeping overview of various kinds of measures for Boolean matrices – algebraic, analytic, and combinatorial – and their relative strengths in pinpointing the communication complexity of specific Boolean functions. Yogesh Dahiya described recent work focusing on the size of decision trees (a measure of the space required for storing Boolean functions), including a surprising application using size bounds in simple decision trees to derandomize depth (i.e. query complexity) in a generalized decision tree model. Avishay Tal described the connection between query and communication complexities via lifting theorems, and sketched a simpler proof of the lifting theorem of Göös, Pitassi, and Watson for randomized query and communication.
Proof Complexity and Circuits
Several connections between proof complexity and circuit complexity were highlighted in a series of talks. For different complexity measures of the same type of object (proofs, circuits, algorithms), tradeoff results describe the extent to which we can optimize one measure while simultaneously controlling the others. Supercritical tradeoffs describe the phenomenon where a procedure optimizing one complexity measure may make other measures shoot up even beyond the generic worst case bound. Jakob Nordström described recent tightening of supercritical tradeoffs in multiple settings, including cutting-plane proof size vs depth, monotone circuit size vs depth, and more; all hinge upon tradeoff results in propositional proof complexity. Susanna de Rezende described a generalized query-to-communication lifting theorem and its applications to obtaining lower bounds for monotone circuits and propositional proof sizes. Olaf Beyersdorff sketched a broad framework for translating computational hardness in varied circuit models into QBFs with no short proofs in QBF proof systems naturally corresponding to many real-world solvers.
Pseudorandomness and Combinatorial Constructions
We had several talks on explicit constructions of pseudorandom combinatorial objects - of the kind that are useful for pseudorandom generators and other derandomization tasks. Rachel Zhang presented her new explicit constant-degree expander graphs, breaking a barrier on what is achievable by spectral methods. Gil Cohen presented a new result computing optimal spectral bounds for the zig-zag product, a method for construct expander graphs. Remarkably, their method uses tools from very distant areas of mathematics: free probability and complex analysis. Siqi Liu showed how high dimensional expanders, a hypergraph analogue of expander graphs, could be used to give new locally testable codes with the pointwise multiplication property. Eshan Chattopadhyay presented explicit constructions of extractors from multiple independent sources, that can extract pure randomness when even just three of them are assumed to be weakly random. This result involves several ideas, and in particular develops extractors that fool multiparty communication protocols. Pavel Pudlák showed that nonmalleable affine extractors, due to their strong pseudorandomness, are hard to compute for certain branching programs. Thomas Thierauf gave a survey of several computational problems surrounding graph rigidity. Finally, Makrand Sinha talked about how to generate pseudorandom matrices using random sequences of elementary operations: the study of such problems is motivated by issues in quantum computation.
Open Problems
The seminar also included an open problems session. Interesting research directions and open problems were posed by Sumegha Garg, Mika Göös, Ian Mertz, Jakob Nordström, Hanlin Ren, and Robert Robere.
The seminar included ample time for informal discussions, and interactions in smaller groups. The discussion spaces in the Schloss were put to good and frequent use!
Social Events
The social interactions during the seminar were significantly enhanced by the traditional and well-attended hike on Wednesday afternoon, and the music night on Thursday night (thanks to Antonina Kolokolova for organizing, and to her and Rahul Ilango, Ian Mertz, Noga Ron-Zewi, Avishay Tal, Roei Tell, Rachel Zhang, for actively contributing to this).
Acknowledgments
The organizers, Swastik Kopparty, Meena Mahajan, Rahul Santhanam, and Till Tantau, thank all participants for the many contributions they made. We also especially thank the Dagstuhl staff, who were - as usual - extremely friendly, helpful, and professional regarding all organizational matters surrounding the seminar. Finally, we are deeply grateful to Ian Mertz for his invaluable help assembling and preparing this report.
Creative Commons BY 4.0
Swastik Kopparty, Meena Mahajan, Rahul Santhanam, and Till Tantau
Computational complexity studies the amount of resources (such as time, space, randomness, communication, or parallelism) necessary to solve discrete problems – a crucial task both in theoretical and practical applications. Despite a long line of research, for many practical problems it is not known if they can be solved efficiently. Here, “efficiently” can refer to polynomial-time algorithms, whose existence is not known for problems like Satisfiability or Factoring. For the large data sets arising for instance in machine learning, already cubic or even quadratic time may be too large, but may be unavoidable as research on fine-grained complexity indicates. The ongoing research on such fundamental problems has a recurring theme: The difficulty of proving lower bounds. Indeed, many of the great open problems of theoretical computer science are, in essence, open lower bound problems.
In this Dagstuhl Seminar, we will address several of the arising questions in the context of circuit and formula sizes, meta-complexity, proof complexity, fine-grained complexity, communication complexity, and classical computational complexity. In each area, powerful tools for proving lower and upper bounds are known, but particularly interesting and powerful results often arise from establishing connections between the fields. By bringing together a diverse group of leading experts and promising young researchers in these areas, the seminar will be an ideal place to discover new, further connections.
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.
Swastik Kopparty, Meena Mahajan, Rahul Santhanam, and Till Tantau
Please log in to DOOR to see more details.
- Olaf Beyersdorff (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Amey Bhangale (University of California - Riverside, US) [dblp]
- Igor Carboni Oliveira (University of Warwick - Coventry, GB) [dblp]
- Amit Chakrabarti (Dartmouth College - Hanover, US) [dblp]
- Sourav Chakraborty (Indian Statistical Institute - Kolkata, IN) [dblp]
- Arkadev Chattopadhyay (TIFR - Mumbai, IN) [dblp]
- Eshan Chattopadhyay (Cornell University - Ithaca, US) [dblp]
- Gil Cohen (Tel Aviv University, IL) [dblp]
- Radu Curticapean (Universität Regensburg, DE) [dblp]
- Yogesh Dahiya (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Susanna de Rezende (Lund University, SE) [dblp]
- Yuval Filmus (Technion - Haifa, IL) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Sumegha Garg (Rutgers University - New Brunswick, US) [dblp]
- Alexander Golovnev (Georgetown University - Washington, DC, US) [dblp]
- Mika Göös (EPFL Lausanne, CH) [dblp]
- Prahladh Harsha (TIFR - Mumbai, IN) [dblp]
- Johan Hastad (KTH Royal Institute of Technology - Stockholm, SE) [dblp]
- Shuichi Hirahara (National Institute of Informatics - Tokyo, JP) [dblp]
- Kaave Hosseini (University of Rochester, US) [dblp]
- Rahul Ilango (MIT - Cambridge, US) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Gillat Kol (Princeton University, US) [dblp]
- Antonina Kolokolova (Memorial University of Newfoundland - St. John's, CA) [dblp]
- Swastik Kopparty (University of Toronto, CA) [dblp]
- Oliver Korten (Columbia University - New York, US) [dblp]
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Sophie Laplante (Université Paris Cité, FR) [dblp]
- Nutan Limaye (IT University of Copenhagen, DK) [dblp]
- Siqi Liu (Institute for Advanced Study - Princeton, US) [dblp]
- Zhenjian Lu (University of Warwick - Coventry, GB) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences & HBNI - Chennai, IN) [dblp]
- Ian Mertz (Charles University - Prague, CZ)
- Jakob Nordström (University of Copenhagen, DK & Lund University, SE) [dblp]
- Pavel Pudlák (The Czech Academy of Sciences - Prague, CZ) [dblp]
- Rüdiger Reischuk (Universität zu Lübeck, DE) [dblp]
- Hanlin Ren (University of Oxford, GB) [dblp]
- Robert Robere (McGill University - Montréal, CA) [dblp]
- Noga Ron-Zewi (University of Haifa, IL) [dblp]
- Michael E. Saks (Rutgers University - Piscataway, US) [dblp]
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Makrand Sinha (University of Illinois - Urbana-Champaign, US)
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Avishay Tal (University of California - Berkeley, US) [dblp]
- Roei Tell (University of Toronto, CA) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Rachel Zhang (MIT - Cambridge, 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 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 28111: Computational Complexity of Discrete Problems (2028-03-12 - 2028-03-17) (Details)
Classification
- Computational Complexity
- Data Structures and Algorithms
- Discrete Mathematics
Keywords
- computational complexity
- circuit complexity
- communication complexity
- lower bounds
- randomness
