Dagstuhl Seminar 22371
Algebraic and Analytic Methods in Computational Complexity
( Sep 11 – Sep 16, 2022 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/22371
Organizers
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE)
- Valentine Kabanets (Simon Fraser University - Burnaby, CA)
- Ronen Shaltiel (University of Haifa, IL)
- Jacobo Torán (Universität Ulm, DE)
Contact
- Michael Gerke (for scientific matters)
- Christina Schwarz (for administrative matters)
Introduction
The seminar on algebraic methods in computational complexity has traditionally taken place every two years in Dagstuhl for many years. In these meetings, we try to bring together leading researchers in a very active and broad area of theoretical computer science, having the algebraic methods as a unifying thread. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar can play an important role in educating a diverse community about the latest new techniques, spurring further progress. For the year 2022, we added a new direction that focused besides the algebraic aspect also on methods from analysis. The seminar brought together more than 40 researchers covering a wide spectrum of complexity theory. We had 24 talks, most of them lasting about 45 minutes, leaving ample room for discussions. In the following we describe the major topics of discussion in more detail.
Some areas of focus
Computational complexity is a fundamental and active subarea of theoretical computer science that has produced some of the most well known results in theoretical computer science in recent years. Here we discuss a few broad themes which highlight the importance of algebra as well as analytic methods in computational complexity, and which represent some focus areas of our present seminar.
Circuit complexity
Boolean circuits are one of the most fundamental model of computation. Due to its 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. In the seminar, we talked about recent results in circuit complexity.
Andrej Bogdanov talked about property testing. He constructed a natural tester that tells if a function from {0, 1}n to some Abelian group is linear (or far from linear).
Frederic Green proved a new correlation bound for certain exponential sums over characteristic 5.
William Hoza presented the construction of a Boolean function F on n bits such that F can be computed by a uniform depth-(d+1) AC0 circuit with O(n) wires, but F cannot be computed by any depth-d TC0 circuit with n1 + γ wires, where γ = 2−Θ(d) and d = o(loglogn).
Michal Koucký dealt with a classical problem, the simulation of Turing machines by circuits. He gave a new simple proof for the classical result that Turing machines running in time t(n) and space s(n) can be simulated by Boolean circuits of size O(t(n)logs(n)) and of depth O(t(n)).
Meena Mahajan presented relations between the minimum rank of a decision tree computing a Boolean function and other complexity measures of the function, as well as a new composition theorem in terms of rank and decision tree depth.
In his talk, Rocco Servedio establish a new quantitative version of the Gaussian correlation inequality. It gives a lower bound on the correlation of two centrally symmetric convex sets based on their "common influential directions".
A new family of sampling tasks was presented by . He showed that any non-trivial algorithmic solutions to tasks from this family imply new uniform lower bounds such as "NP not in uniform ACC0" or "NP does not have uniform depth-2 threshold circuits".
Algebraic complexity
A class of circuits especially suited for the use of algebraic techniques is that of arithmetic circuits. These are circuit models that compute polynomial functions by using gates performing arithmetic operations (additions, subtractions, multiplications, divisions, etc.) Two fundamental complexity measures for arithmetic circuits are the size and the depth or product depth.
Prerona Chatterjee considered the question of proving lower bounds against non-commutative circuits better than Ω(nlogn). She showed a quadratic lower bound against the n-variate central symmetric polynomial.
Arkadev Chattopadhyay talked about connections between communication complexity measures and monotone arithmetic circuit lower bounds. He constructed a (set-multilinear) monotone polynomial that can be computed by depth-3 multilinear formulas in sub-cubic size but requires exponential size to be computed by monotone arithmetic circuits. Second, he proved the existence of a polynomial over n variables in VNP, for which 2Ω(n) size ϵ-sensitive lower bounds hold if ϵ = 2−O(n).
Barrier results in the group-theoretic approach to bounding the exponent of matrix multiplication was the topic of the talk by Chris Umans . He showed that finite groups of Lie type cannot prove ω = 2 and presented a further barrier result. Then he gave constructions in the continuous setting, which can potentially evade these two barriers.
Pascal Koiran studied the decomposition of multivariate polynomials as sums of powers of linear forms. He presented a randomized algorithm for the following problem: Given a homogeneous polynomial of degree d as a blackbox, decide whether it can be written as a linear combination of dth powers of linearly independent complex linear forms.
Nutan Limaye proved in her talk that there exist monomial symmetric polynomials that are hard for the class VNP.
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 it is easy to construct one by random sampling, but a very important problem is to get efficient deterministic constructions.
Eric Allender proved that Kolmogorov complexity characterizes statistical zero knowledge. Every decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible to a promise problem for Kolmogorov-random strings.
Random walks on expanders are a useful tool in complexity theory. Gil Cohen explained how the inherent cost can be reduced from exponential to linear by applying a permutation after each random step.
Sylvester-Gallai type problems have found applications in polynomial identity testing and coding theory. Rafael Oliveira discussed such problems and their relation to algebraic computation, and presented a theorem that radical Sylvester-Gallai configurations for cubic polynomials must have small dimension.
Ryan O'Donnell explained how to contruct high-dimensional expanders from Chevalley groups.
Motivated by applications from cryptography, Noga Ron-Zewi studied a new interactive variant of PCPs, so-called interactive oracle proofs. She showed that for this model the overhead in the encoding can be made arbitrarily small and the prover complexity overhead can be made constant.
In his talk, Amon Ta-Shma gave an alternative construction of the lossless condenser by Guruswami, Umans and Vadhan. Instead of Parvaresh-Vardy codes, the new construction is based on multiplicity codes.
A Chor-Goldreich source is a sequence of random variables where each has min-entropy, even conditioned on the previous ones. David Zuckerman showed how to extend this notion in several ways, most notably allowing each random variable to have Shannon entropy conditioned on previous ones. He then proved new pseudorandomness results for Shannon-CG sources.
Border complexity and invariant theory
Many problems in algebraic complexity theory can be written as an orbit closure problem. We are given a vector space V and a group G acting on it. The orbit Gv of an element v ∈ V is the set {gv | g ∈ G} and its closure is the usual closure in the Zariski topology. For instance, we can formulate the tensor border rank problem in this language: Alder and Strassen proved that the question whether a tensor t has border rank ≤ r is equivalent to deciding whether t is in the orbit closure (under the standard action GLn × GLn × GLn) of the so-called unit tensor of size r. As second example is provided by Mulmuley and Sohoni who formulated a variant of the permanent versus determinant question as an orbit closure problem.
Peter Bürgisser gave an introduction to new algorithmic and analysis techniques that extend convex optimization from the classical Euclidean setting to a general geodesic setting. He pointed out the relevance of invariant and representation theory for for complexity theory and highlighted connections to different areas of mathematics, statistics, computer science, and physics.
Rohit Gurjar considered determinants of the matrices of the form (∑iAixi) where each Ai is rank one. He showed that this class of polynomials is closed under approximation.
Approximate complexity was also the topic of Nitin Saxena talk. He proved that the border of bounded-top-fanin depth-3 circuits is relatively easy, since it can be computed by a polynomial-size algebraic branching program.
Counting and quantum complexity
In order to study the #P (non-)membership of some concrete problems, Christian Ikenmeyer started the development of a classification of the #P closure properties on affine varieties. He obtained oracle separations between counting classes, where the existence of the oracle is based on properties of the vanishing ideal of an affine variety.
Steve Fenner considered a problem in quantum computing, the construction of a ``realistic'' Hamiltonian for quantum fanout.
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 it has hopefully 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 workshop. We look forward to our next seminar.
Creative Commons BY 4.0
Markus Bläser, Valentine Kabanets, 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 Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples.
The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so called "chasm at depth 4" suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model (and these are tied to central questions regarding the power of randomness in computation).
Another surprising connection is that the algebraic techniques invented to show lower bounds now prove useful to develop efficient algorithms. For example, Williams showed how to use the polynomial method to obtain faster all-pair-shortest-path algorithms.
Beside algebraic methods, analytic methods have been used for quite some time in theoretical computer science. Very recently, Fourier analysis was essential for proving a variant of the famous Unique Games Conjecture, the so-called 2-2 Conjecture.
Analytic methods can also be used to solve algebraic problems. Garg et al. use analytic scaling algorithms to solve problems from algebra, so-called orbit closure problems, by using geometric invariant theory to establish the link. Central problems, like the tensor border rank or non-commutative identity testing, can be written as such an orbit closure problem.
These new directions will be in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 18391. 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 this seminar will play an important role in educating a diverse community about the latest new techniques, spurring further progress.
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán
- Eric Allender (Rutgers University - Piscataway, US) [dblp]
- Markus Bläser (Universität des Saarlandes - Saarbrücken, DE) [dblp]
- Andrej Bogdanov (The Chinese University of Hong Kong, HK) [dblp]
- Peter Bürgisser (TU Berlin, DE) [dblp]
- Prerona Chatterjee (The Czech Academy of Sciences - Prague, CZ) [dblp]
- Arkadev Chattopadhyay (TIFR - Mumbai, IN) [dblp]
- Gil Cohen (Tel Aviv University, IL) [dblp]
- Julian Dörfler (Universität des Saarlandes - Saarbrücken, DE)
- Stephen A. Fenner (University of South Carolina - Columbia, US) [dblp]
- Michael A. Forbes (University of Illinois - Urbana-Champaign, US) [dblp]
- Lance Fortnow (Illinois Institute of Technology, US) [dblp]
- Anna Gál (University of Texas - Austin, US) [dblp]
- Frederic Green (Clark University - Worcester, US) [dblp]
- Rohit Gurjar (Indian Institute of Technology - Mumbai, IN) [dblp]
- William Hoza (University of California - Berkeley, US) [dblp]
- Christian Ikenmeyer (University of Liverpool, GB) [dblp]
- Valentine Kabanets (Simon Fraser University - Burnaby, CA) [dblp]
- Pascal Koiran (ENS - Lyon, FR) [dblp]
- Antonina Kolokolova (University of Newfoundland, CA) [dblp]
- Michal Koucký (Charles University - Prague, CZ) [dblp]
- Sophie Laplante (University Paris Diderot, FR) [dblp]
- Nutan Limaye (IT University of Copenhagen, DK) [dblp]
- Meena Mahajan (The Institute of Mathematical Sciences - Chennai, IN) [dblp]
- Rafael Mendes de Oliveira (University of Waterloo, CA) [dblp]
- Ryan O'Donnell (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Natacha Portier (ENS - Lyon, FR) [dblp]
- Noga Ron-Zewi (University of Haifa, IL) [dblp]
- Rahul Santhanam (University of Oxford, GB) [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]
- Srikanth Srinivasan (Aarhus University, DK) [dblp]
- Amnon Ta-Shma (Tel Aviv University, IL) [dblp]
- Jacobo Torán (Universität Ulm, DE) [dblp]
- Christopher Umans (California Institute of Technology - Pasadena, US) [dblp]
- Mary Wootters (Stanford University, US) [dblp]
- David Zuckerman (University of Texas - Austin, US) [dblp]
- Jeroen Zuiddam (University of Amsterdam, NL) [dblp]
Related Seminars
- 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 24381: Algebraic and Analytic Methods in Computational Complexity (2024-09-15 - 2024-09-20) (Details)
Classification
- Computational Complexity
Keywords
- computational complexity
- algebra
- (de-)randomization
- circuits
- coding
