##### Dagstuhl Seminar 22371

### Algebraic and Analytic Methods in Computational Complexity

##### ( Sep 11 – Sep 16, 2022 )

##### Permalink

##### 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 AC^{0}[*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) AC^{0} circuit with *O*(*n*) wires, but *F* cannot be computed by any
depth-*d* *T**C*^{0} circuit with
*n*^{1 + γ}
wires, where *γ* = 2^{−Θ(d)}
and *d* = *o*(loglog*n*).

*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*)log*s*(*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 ACC^{0}" 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 *Ω*(*n*log*n*). 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 *G**v* of an element *v* ∈ *V* is the set {*g**v* | *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 GL_{n} × GL_{n} × GL_{n})
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 (∑_{i}*A*_{i}*x*_{i})
where each *A*_{i} 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.

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.

- 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