Dagstuhl-Seminar 24381
Algebraic and Analytic Methods in Computational Complexity
( 15. Sep – 20. Sep, 2024 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/24381
Organisatoren
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE)
- Shubhangi Saraf (University of Toronto, CA)
- Ronen Shaltiel (University of Haifa, IL)
- Jacobo Torán (Universität Ulm, DE)
Kontakt
- Michael Gerke (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
The seminar brought together more than 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed the great importance of such techniques for theoretical computer science. We had 27 talks, most of them lasting about 35 minutes, leaving ample room for discussions. We also scheduled several longer talks of a more introductory nature. One of the days, we also had a much appreciated open problem session.
Computational complexity is a fundamental and active area of research that has produced some of the most well known results in theoretical computer science in recent years. Here we discuss a few broad themes that represented the focus areas of our seminar, mentioning some of the given talks in these areas.
Circuit complexity
Boolean circuits are one of the most fundamental models of computation. Due to their combinatorial nature, they seem more amenable to formal analysis than the uniform models such as Turing machines. The classical lower bound techniques of Razborov and Smolensky are algebraic: they work by first approximating AC0[p] circuits (constant-depth circuits with AND, OR, NOT, and counting modulo prime p gates) by low-degree polynomials, and then proving that certain functions (like Majority) are not well correlated with such polynomials. The Fourier expansion of a Boolean function and its representation as a real multilinear polynomial as well as other analytic tools have been added in the last years to the bag of tools used for the analysis of Boolean circuits. Several seminar talks discussed recent results on circuit complexity.
Igor Carboni Oliveira established that efficient indistinguishability obfuscation for multi-output circuits necessarily incurs an additive size overhead of Ω(s/log s) under reasonable complexity assumptions.
In his talk, William Hoza studied hardness amplification in the context of two well-known “moderate” average-case hardness results for AC0 circuits.
Algebraic complexity
A class of circuits especially suitable for the use of algebraic techniques is that of arithmetic or algebraic circuits. These are circuit models that compute polynomial functions using gates performing arithmetic operations (additions, subtractions, multiplications, and divisions). Two fundamental complexity measures for arithmetic circuits are size and depth.
Robert Andrews talked about constant-depth arithmetic circuits for linear algebra problems. He explained a new algorithm for the GCD that uses a combination of polynomial interpolation and Newton’s identities for symmetric polynomials.
Vishwas Bhargava talked about read-once branching programs, a special class of arithmetic circuits. His focus was the order in which variables can appear in such branching programs.
Exponential lower bounds against sums of ordered set-multilinear branching programs were shown by Prerona Chatterjee. Her bound stays superpolynomial for degree ω(log n), complementing recent results by Bhargav, Dwivedi, and Saxena.
Chris Umans talked about the group-theoretic approach to fast matrix multiplication and how to extend the group-theoretic framework to the setting of infinite groups.
In his presentation, Michael Forbes explained how to extend the recent breakthrough of Limaye, Srinivasan, and Tavenas, who gave the first super-polynomial lower bounds against low-depth algebraic circuits, to fields of small characteristic. This answers an open question by Limaye, Srinivasan, and Tavenas.
In his talk, Rafael Mendes de Oliveira surveyed the connections between Sylvester-Gallai configurations and complexity theory as well as identity testing.
Peter Bürgisser studied the computational complexity of robust generalizations of orbit problems, which amount to approximating the distance of orbits in Cn up to a factor γ ≥ 1. These algorithms run in polynomial time if and only if a version of the famous number-theoretic abc-conjecture holds.
In his talk, Nitin Saxena showed that the border of bounded-top-fanin depth-3 circuits can be computed by polynomial-size algebraic branching programs, which has applications especially in identity testing and lower bounds.
Amir Shpilka proved that for polynomials f, g ∈ C[x] such that g divides f, the bit complexity of the quotient polynomial h = f/g is bounded by the sparsity of g and the sparse representation size of f.
Pseudorandomness and derandomization
The theory of pseudorandomness studies explicit constructions and applications of “random-like” objects of combinatorial or algebraic type. The common feature of such objects is that they are easy to construct by random sampling, but it is a very important problem to get efficient deterministic constructions.
Arkadev Chattopadhyay discussed the power of randomness for computing total Boolean functions in two models of computation, query algorithms and 2-party communication protocols.
In his talk, Gil Cohen used analytic techniques to explore a more refined analysis of the zig-zag graph product, that leverages the entire spectrum of the graph.
Dean Doron studied almost Chor–Goldreich (CG) random sources, and constructed deterministic condensers with constant entropy gap for them. As a consequence, one can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown.
Seedless condenser were studied by Eshan Chattopadhyay, proving several new results for seedless condensers in the context of three related classes of sources.
Rohit Gurjar gave a characterization of principal minor equivalence and constructed a deterministic polynomial time algorithm to check if two given matrices are principal minor equivalent, which can be viewed as some sort of identity testing.
Error correcting codes
Error-correcting codes, particularly those constructed from polynomials, lie at the heart of many of the most significant results in computational complexity, like interactive proofs, PCPs, hardness amplification, or explicit constructions.
In his talk, Mrinal Kumar showed that univariate multiplicity codes can be list-decoded up to capacity in nearly linear time.
In her talk, Noga Ron-Zewi surveyed the theory behind the recent result that Reed-Solomon codes with random evaluation points are list-decodable up to capacity with optimal list size, and then discussed how it can be extended to the whole class of polynomial ideal codes.
Jad Sidblak studied codes against channels that are computationally bounded. He constructed codes with optimal rate that are explicit (assuming circuit lower bounds).
Srikanth Srinivasan presented low-degree local correction algorithms for constant-degree polynomials from {0, 1}n to any field.
Roei Tell talked about simulations of interactive proof systems by non-interactive proof systems. He explained how to leverage approaches from recent works in derandomization to address this problem.
Further applications of algebraic methods
In addition to the focus areas mentioned above, we had a number of talks that considered applications of algebraic methods in other areas. In particular, we had a significant number of contributions that dealt with learning problems.
The talk of Neeraj Kayal explored machine learning tasks from the perspective of algebraic complexity, particularly using techniques based on arithmetic circuit lower bounds.
Pascal Koiran gave a new constructive uniqueness theorem for tensor decomposition. As a result, he obtained the first efficient algorithm for the so-called overcomplete decomposition of generic tensors of order 3.
Michal Koucký presented an efficient randomized algorithm for computing hierarchical Hamming sketches, which has applications in the construction of sketches for the edit distance.
The topic of the talk by Meena Mahajan was lower bounds for the polynomial calculus over non-Boolean domains. She showed how to improve a recent work by Sokolov by using an asymmetric gadget, obtaining a stronger lower bound that works over any field.
Kilian Rothmund presented an NC algorithm for testing whether a graph is minimally rigid when the input graph is K3, 3-free.
Rocco Servedio showed that the supremum of any centered Gaussian process can be approximated to any arbitrary accuracy by a finite dimensional Gaussian process, where the dimension of the approximator just depends on the target error.
Conclusion
The talks of the seminar ranged over a broad assortment of subjects with the underlying theme of using algebraic and analytic techniques. It was a very fruitful meeting and has, we hope, initiated new directions in research. Several participants specifically mentioned that they appreciated the particular focus on a common class of techniques (rather than end results) as a unifying theme of the seminar. We look forward to our next seminar.
Creative Commons BY 4.0
Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, and Jacobo Torán
Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures. It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques.
The algebraic theme continues to play a central role in some of the most exciting recent progress in computational complexity in areas like circuit complexity, polynomial identity testing, pseudorandomness and derandomization or error correcting codes.
Beside algebraic methods, analytic methods like Fourier analysis have been used for quite some time in theoretical computer science. These methods have been used recently in some breakthrough results in complexity theory in areas like hardness of approximation, quantum computation and scaling algorithms.
A new theme that has gained importance in the last years is the area of meta-complexity, that is, the complexity of computational problems that are themselves problems about the complexity of computation. Meta-complexity provides a link between a variety of important areas like circuit complexity, proof complexity, cryptography, and learning theory.
These new directions will be in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 22371. Taking the recent exciting developments outlined above into account, we also include analytic methods this time.
This Dagstuhl Seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and analytic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and we hope that this seminar will contribute in educating a diverse community about the latest new techniques.
Markus Bläser, Shubhangi Saraf, Ronen Shaltiel, and Jacobo Torán
Please log in to DOOR to see more details.
- Robert Andrews (University of Waterloo, CA) [dblp]
- Vikraman Arvind (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Vishwas Bhargava (University of Waterloo, CA) [dblp]
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Andrej Bogdanov (University of Ottawa, CA) [dblp]
- Harry Buhrman (University of Amsterdam, NL) [dblp]
- Peter Bürgisser (TU Berlin, DE) [dblp]
- Igor Carboni Oliveira (University of Warwick - Coventry, GB) [dblp]
- Prerona Chatterjee (NISER - Bhubaneswar, 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]
- Dean Doron (Ben Gurion University - Beer Sheva, IL) [dblp]
- Klim Efremenko (Ben Gurion University - Beer Sheva, IL) [dblp]
- Michael A. Forbes (University of Illinois - Urbana-Champaign, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Rohit Gurjar (Indian Institute of Technology Bombay - Mumbai, IN) [dblp]
- Shuichi Hirahara (National Institute of Informatics - Tokyo, JP) [dblp]
- William Hoza (University of Chicago, US) [dblp]
- Christian Ikenmeyer (University of Warwick - Coventry, GB) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Neeraj Kayal (Microsoft Research India - Bangalore, IN) [dblp]
- Pascal Koiran (ENS - Lyon, FR) [dblp]
- Antonina Kolokolova (Memorial University of Newfoundland - St. John's, CA) [dblp]
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Donald Kougang Yombi (AIMS Rwanda - Kigali, RW) [dblp]
- Mrinal Kumar (TIFR Mumbai, IN) [dblp]
- Nutan Limaye (IT University of Copenhagen, DK) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Or Meir (University of Haifa, IL) [dblp]
- Rafael Mendes de Oliveira (University of Waterloo, CA) [dblp]
- Noga Ron-Zewi (University of Haifa, IL) [dblp]
- Kilian Rothmund (Hochschule Aalen, DE)
- Rahul Santhanam (University of Oxford, GB) [dblp]
- Ramprasad Saptharishi (TIFR Mumbai, IN) [dblp]
- Shubhangi Saraf (University of Toronto, CA) [dblp]
- Nitin Saxena (Indian Institute of Technology Kanpur, IN) [dblp]
- Rocco Servedio (Columbia University - New York, US) [dblp]
- Ronen Shaltiel (University of Haifa, IL) [dblp]
- Amir Shpilka (Tel Aviv University, IL) [dblp]
- Jad Silbak (Northeastern University - Boston, US) [dblp]
- Srikanth Srinivasan (University of Copenhagen, DK) [dblp]
- Sathyawageeswar Subramanian (University of Cambridge, GB) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Sébastien Tavenas (University Savoie Mont Blanc - Le Bourget-du-Lac, FR) [dblp]
- Roei Tell (University of Toronto, CA) [dblp]
- Thomas Thierauf (Hochschule Aalen, DE) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (California Institute of Technology - Pasadena, US) [dblp]
- Jeroen Zuiddam (University of Amsterdam, NL) [dblp]
Verwandte Seminare
- Dagstuhl-Seminar 02421: Algebraic Methods in Quantum and Classical Models of Computation (2002-10-13 - 2002-10-18) (Details)
- Dagstuhl-Seminar 04421: Algebraic Methods in Computational Complexity (2004-10-10 - 2004-10-15) (Details)
- Dagstuhl-Seminar 07411: Algebraic Methods in Computational Complexity (2007-10-07 - 2007-10-12) (Details)
- Dagstuhl-Seminar 09421: Algebraic Methods in Computational Complexity (2009-10-11 - 2009-10-16) (Details)
- Dagstuhl-Seminar 12421: Algebraic and Combinatorial Methods in Computational Complexity (2012-10-14 - 2012-10-19) (Details)
- Dagstuhl-Seminar 14391: Algebra in Computational Complexity (2014-09-21 - 2014-09-26) (Details)
- Dagstuhl-Seminar 16411: Algebraic Methods in Computational Complexity (2016-10-09 - 2016-10-14) (Details)
- Dagstuhl-Seminar 18391: Algebraic Methods in Computational Complexity (2018-09-23 - 2018-09-28) (Details)
- Dagstuhl-Seminar 22371: Algebraic and Analytic Methods in Computational Complexity (2022-09-11 - 2022-09-16) (Details)
Klassifikation
- Computational Complexity
Schlagworte
- computational complexity
- algebra
- (de-)randomization
- circuits
- coding theory
