Algebraic and Analytic Methods in Computational 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 ${\mathrm{𝖠𝖢}}^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. 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 $\mathrm{\Omega }(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 ${\mathrm{𝖠𝖢}}^0$ circuits.

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 $\omega (\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 $C^n$ up to a factor $\gamma \ge 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\in 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$.

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, 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.

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 $\mathrm{𝖭𝖢}$ algorithm for testing whether a graph is minimally rigid when the input graph is $K_{3,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.

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.

How does one compute the greatest common divisor (GCD) of two univariate polynomials? The Euclidean algorithm provides a polynomial-time solution, and fast variants of the Euclidean algorithm can solve this problem in nearly-linear time. The GCD can also be expressed in a linear-algebraic form. Basic tasks in linear algebra like computing determinants and solving linear systems can be performed in $𝒪({\log }^{2}n)$ parallel time, and this can be used to compute the GCD in $𝒪({\log }^{2}n)$ parallel time. This algorithm does not take advantage of any structure present in the resulting linear systems, so in principle one could compute the GCD in parallel even faster.

In this talk, I will describe a new algorithm that computes the GCD in $𝒪(\log n)$ parallel time by using a combination of polynomial interpolation and Newton’s identities for symmetric polynomials. In fact, this algorithm can essentially be implemented as an arithmetic circuit of constant depth. Similar ideas yield constant-depth circuits to compute the resultant, Bézout coefficients, and squarefree decomposition.

Univariate multiplicity codes are a family of algebraic error correcting codes that are obtained by evaluating low degree univariate polynomials and all their derivatives up to a certain order at a set of distinct input points in an underlying field. These codes are a well studied generalisation of the more well known Reed-Solomon codes and are now known to have amazing list decodable properties; specifically, they are known to be efficiently list decodable up to the so-called list decoding capacity with constant list size.

In this talk, I will discuss a recent joint work with Rohan Goyal, Prahladh Harsha and Ashutosh Shankar, where we show that these codes can be list decoded up to capacity in nearly linear time. On the way, we will talk about lattices over the univariate polynomial ring, and will see a nearly linear time algorithm for solving linear differential equations of high order.

ROABPs are a natural model of computation, beloved for their analogies to Boolean ROBPs, their ability to subsume many interesting subclasses, and most notably for Nisan’s criterion, which can pinpoint the ROABP-complexity for any fixed order.

However, much less is understood about finding the order, and the subclasses of ROABPs that are order-oblivious, which will be the focus of this talk.

First, we will demonstrate that determining the order of an ROABP is an $\mathrm{𝖭𝖯}$-hard problem. Following that, we will explore the computational power of commutative ROABPs, particularly their ability to compute polynomials with small partial derivative dimension.

We consider indistinguishability obfuscation (iO) for multi-output circuits $C$ of size $s$, where $s$ is the number of AND/OR/NOT gates in $C$. Under the worst-case assumption that $\mathrm{𝖭𝖯}$ is not contained in $\mathrm{𝖡𝖯𝖯}$, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size $s+o(s/\log s)$. In other words, to be secure, an efficient iO scheme must incur an $\mathrm{\Omega }(s/\log s)$ additive overhead in the size of the obfuscated circuit. The hardness assumption under which this negative result holds is minimal since an optimal iO scheme with no circuit size overhead exists if $\mathrm{𝖭𝖯}$ is contained in $\mathrm{𝖡𝖯𝖯}$.

Expanding on this result, we also rule out iO for single-output database-aided circuits with an arbitrary polynomial overhead in circuit size. This strengthens an impossibility result by Goldwasser and Rothblum (2007), which considered circuits with access to an exponential-length database that the obfuscator has oracle access to; in contrast, our impossibility result holds even w.r.t. polynomial-size databases and even w.r.t. obfuscators that may run in time polynomial in the size of the database (and thus may read the whole database).

The proof of our main result builds on a connection between obfuscation and meta-complexity put forward by Mazor and Pass (2024), and on the $\mathrm{𝖭𝖯}$-hardness of circuit minimization for multi-output circuits established by Loff, Ilango, and Oliveira (2020), together with other techniques from cryptography and complexity theory.

Algebraic Branching Programs (ABPs) are a natural model for computing polynomials formally, and proving super-polynomial lower bounds against this model is a central question in the field of algebraic complexity theory.

In a recent work, Bhargav, Dwivedi, and Saxena (2023), showed that super-polynomial lower bounds against a sum of ordered set-multilinear branching programs – for a polynomial over $n$ variables of degree $𝒪(\log n/\log \log n)$ – would imply super-polynomial lower bounds against general ABPs. Following up on their work, in a joint work with Kush, Saraf and Shpilka, we prove an exponential lower bound against this model but for a polynomial over $n^2$ variables of degree $n$. In fact, even though our lower bound does not remain super-polynomial when the polynomial has degree $𝒪(\log n/\log \log n)$, it does remain so for a polynomial with degree as low as $\omega (\log n)$. Moreover, the hard polynomial is computable by an ABP, thereby suggesting that our approach would not work if one wanted to prove lower bounds against general ABPs.

In this talk, we will discuss our results in the context of proving general ABP lower bounds and also give a brief overview of the proofs. The talk is based on joint work with Deepanshu Kush, Shubhangi Saraf and Amir Shpilka.

Understanding the power of randomness for general algorithms is one of the central themes of the theory of computation but is still seemingly widely out of reach. We consider the power of randomness for computing total Boolean functions in two simple, very well studied models of computation: query algorithms and $2$-party communication protocols. In the former, it is known that randomness does not give super-polynomial advantage, whereas in the latter, it does, thanks to the Equality function. While these facts are folklore by now, we argue that this doesn’t mean that we understand the power of randomness satisfactorily in these simple models.

For instance, Goos-Pitassi-Watson (2016) asked if ${𝖯}^{\mathrm{𝖭𝖯}}$ protocols can simulate every $\mathrm{𝖡𝖯𝖯}$ protocol. It was not even known if ${𝖯}^{\mathrm{𝖤𝖰}}$ contained $\mathrm{𝖡𝖯𝖯}$. We (Chattopadhyay-Lovett-Vinyals, 2019) give a strong negative answer to that. In the query world, motivated by the recent work of Knop-Lovett-McGuire-Yuan (2021), we consider models that could be thought of as intermediates between query and communication protocols, by allowing the queries to be more powerful. For example, when the set of available query functions are AND (OR) functions or both AND and OR functions. In this case, we (Chattopadhyay-Dahiya-Mande-Radhakrishnan-Sanyal, 2023) show that randomness does not give significant advantage for computing functions. On the other hand, it is known that randomness provides exponential advantage in the model of parity decision trees (PDT).

We conjecture that the set of boolean functions that can be computed by poly-log depth randomized PDTs are exactly those that can be computed in poly-log depth by decision trees whose query functions are testing membership in affine spaces.

The Cohn–Umans (FOCS ’03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group $G$ satisfying a simple combinatorial condition (the Triple Product Property). The complexity of such an algorithm then depends on the representation theory of $G$. In this paper we extend the group-theoretic framework to the setting of infinite groups. In particular, this allows us to obtain constructions in Lie groups, with favorable parameters, that are provably impossible in finite groups of Lie type (Blasiak, Cohn, Grochow, Pratt, and Umans, ITCS ’23). Previously the Lie group setting was investigated purely as an <analogue of the finite group case; a key contribution in this paper is a fully developed framework for obtaining bona fide matrix multiplication algorithms directly from Lie group constructions.

As part of this framework, we introduce “separating functions” as a necessary new design component, and show that when the underlying group is $G={\mathrm{𝖦𝖫}}_n$, these functions are polynomials with their degree being the key parameter. In particular, we show that a construction with “half-dimensional” subgroups and optimal degree would imply $\omega =2$. We then build up machinery that reduces the problem of constructing optimal-degree separating polynomials to the problem of constructing a single polynomial (and a corresponding set of group elements) in a ring of invariant polynomials determined by two out of the three subgroups that satisfy the Triple Product Property. This machinery combines border rank with the Lie algebras associated with the Lie subgroups in a critical way.

We give several constructions illustrating the main components of the new framework, culminating in a construction in a special unitary group that achieves separating polynomials of optimal degree, meeting one of the key challenges. The subgroups in this construction have dimension approaching half the ambient dimension, but (just barely) too slowly. We argue that features of the classical Lie groups make it unlikely that constructions in these particular groups could produce nontrivial bounds on $\omega$ unless they prove $\omega =2$. One way to get $\omega =2$ via our new framework would be to lift our existing construction from the special unitary group to ${\mathrm{𝖦𝖫}}_n$, and improve the dimension of the subgroups from $\frac{dimG}{2}-\mathrm{\Theta }(n)$ to $\frac{dimG}{2}-o(n)$.

The Zig-Zag product and related graph operators, such as derandomized squaring, are inherently combinatorial, and the classical bounds on their behavior typically require a blend of combinatorics and linear algebra. However, these bounds often fail to align with experimental results.

In this talk, we will explore a more refined analysis that leverages the entire spectrum of the graph (rather than just its spectral expansion), yielding results that both match experimental observations and, in some sense, are tight. The technique is analytic, deviating from the classical techniques: for the upper bound, we utilize finite free probability, while for the lower bound, we draw on results from analytic combinatorics.

No prior knowledge is assumed. This talk is based on joint works with Itay Cohen and Gal Maor.

We consider the following adversarial, non-Markovian, random walk on “good enough” expanders: Starting from some fixed vertex, walk according to the instructions $X=X_1,\mathrm{\dots },X_t$, where each $X_i$ is only somewhat close to having only little entropy, conditioned on any, or a typical, prefix. The $X_i$-s are not independent, meaning that the distribution of the next step depends not only on the walk’s current node, but also on the path it took to get there. We show that such walks (or certain variants of them) accumulate most of the entropy in $X$.

More specifically, we study $X$-s that are “almost Chor–Goldreich (CG) sources”, and for them our result gives deterministic condensers (even online ones) with constant entropy gap, which were not known to exist even for standard CG sources. As a consequence, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. For a more general notion of “unpredictability sources”, we show that a random walk with a random stopping time also results in a distribution with constant entropy gap, and that such a random stopping time is necessary.

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, SHELA sources as defined by Aggarwal, Obremski, Ribeiro, Siniscalchi, and Visconti [AORSV, EUROCRYPT’20], and almost Chor-Goldreich (CG) sources as defined by Doron, Moshkovitz, Oh, and Zuckerman [DMOZ, STOC’23]. Here, we will think of these sources as a sequence of random variables $𝐗={𝐗}_1,\mathrm{\dots },{𝐗}_{\mathrm{\ell }}$ on $\mathrm{\ell }$ symbols where at least $g$ out of these $\mathrm{\ell }$ symbols are “good” (i.e., uniformly random), denoted as a $(g,\mathrm{\ell })$-source, and the remaining “bad” $\mathrm{\ell }-g$ symbols may adversarially depend on these $g$ good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions.

Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [DMOZ, STOC’23] which explicitly constructs a seedless condenser for a restricted subset of $(g,\mathrm{\ell })$-almost CG sources.

The following are our main results concerning seedless condensers for each of these three sources.

1. 1.

   When $g\le \mathrm{\ell }/2$, we prove for all three classes of sources that condensing with error 0.99 above rate $\frac{1}{\lfloor \mathrm{\ell }/g\rfloor }$ is impossible.

2. 2.

   Next, we investigate the setting of $g>\mathrm{\ell }/2$, and in particular focus on $g=2$ and $\mathrm{\ell }=3$. We show that condensing with constant error above rate $\frac{2}{3}$ is impossible for uniform NOSF sources.

3. 3.

   Quite surprisingly, we show the existence of excellent condensers for uniform $(2,3)$-SHELA and uniform almost CG sources, thus proving a separation from NOSF sources. Further, we explicitly construct a condenser that outputs $m=\frac{n}{16}$ bits and condenses any uniform $(2,3)$-SHELA source to entropy $m--𝒪(\log (m/\epsilon ))$ (with error $\epsilon$). Our construction is based on a new type of seeded extractor that we call output-light, which could be of independent interest. In contrast, we show that it is impossible to extract from uniform $(2,3)$-SHELA sources.

These results extend seedless extractor lower bounds on NOSF sources (Bourgain, Kahn, Kalai, Katznelson, and Linial [BKKKL, Israel J. Math’92]) and make progress on several open question from [DMOZ, STOC’23], [AORSV, EUROCRYPT’20], and Kopparty and N [KN, RANDOM’23].

The recent breakthrough of Limaye, Srinivasan and Tavenas [Limaye et al., 2022] (LST) gave the first super-polynomial lower bounds against low-depth algebraic circuits, for any field of zero (or sufficiently large) characteristic. It was an open question to extend this result to small-characteristic ([Limaye et al., 2022; Govindasamy et al., 2022; Fournier et al., 2023]), which in particular is relevant for an approach to prove superpolynomial ${\mathrm{𝖠𝖢}}^0[p]$-Frege lower bounds ([Govindasamy et al., 2022]). In this work, we prove super-polynomial algebraic circuit lower bounds against low-depth algebraic circuits over any field, with the same parameters as LST (or even matching the improved parameters of Bhargav, Dutta, and Saxena [Bhargav et al., 2022]). We give two proofs. The first is logical, showing that even though the proof of LST naively fails in small characteristic, the proof is sufficiently algebraic that generic transfer results imply the result over characteristic zero implies the result over all fields. Motivated by this indirect proof, we then proceed to give a second constructive proof, replacing the field-dependent set-multilinearization result of LST with a set-multilinearization that works over any field, by using the Binet-Minc identity [Minc, 1979].

Two matrices are said to be principal minor equivalent if they have equal corresponding principal minors of all orders. We give a characterization of principal minor equivalence and a deterministic polynomial time algorithm to check if two given matrices are principal minor equivalent.

Earlier such results were known for certain special cases like symmetric matrices, skew-symmetric matrices with 0, 1, -1-entries, and matrices with no cuts (i.e., for any non-trivial partition of the indices, the top right block or the bottom left block must have rank more than 1).

As an application, we give a deterministic polynomial-time test to check equality of two multivariate polynomials, each computed by a symbolic determinant with a rank 1 constraint on coefficient matrices.

We study hardness amplification in the context of two well-known “moderate” average-case hardness results for ${\mathrm{𝖠𝖢}}^0$ circuits. First, we investigate the extent to which ${\mathrm{𝖠𝖢}}^0$ circuits of depth $d$ can approximate ${\mathrm{𝖠𝖢}}^0$ circuits of some larger depth $d+k$. The case $k=1$ is resolved by Håstad, Rossman, Servedio, and Tan’s celebrated average-case depth hierarchy theorem [1]. Our contribution is a significantly stronger correlation bound when $k\ge 3$. Specifically, we show that there exists a linear-size ${\mathrm{𝖠𝖢}}_{d+k}^0$ circuit $h:{\{0,1\}}^n\to \{0,1\}$ such that for every ${\mathrm{𝖠𝖢}}_d^0$ circuit $g$, either $g$ has size $\exp (n^{\mathrm{\Omega }(1/d)})$, or else $g$ agrees with $h$ on at most a $(1/2+\epsilon )$-fraction of inputs where $\epsilon =\exp (-(1/d)\cdot \mathrm{\Omega }{(\log n)}^{k--1})$. For comparison, Håstad, Rossman, Servedio, and Tan’s result has $\epsilon =n^{-\mathrm{\Theta }(1/d)}$. Second, we consider the majority function. It is well known that the majority function is moderately hard for ${\mathrm{𝖠𝖢}}^0$ circuits (and stronger classes). Our contribution is a stronger correlation bound for the XOR of $t$ copies of the $n$-bit majority function, denoted ${\mathrm{𝖬𝖠𝖩}}_n^{\oplus t}$. We show that if $g$ is an ${\mathrm{𝖠𝖢}}_d^0$ circuit of size $S$, then $g$ agrees with ${\mathrm{𝖬𝖠𝖩}}_n^{\oplus t}$ on at most a $(1/2+\epsilon )$-fraction of inputs, where $\epsilon ={\left(O{(\log S)}^{d--1}/\sqrt{n}\right)}^t$.

To prove these results, we develop a hardness amplification technique that is tailored to a specific type of circuit lower bound proof. In particular, one way to show that a function $h$ is moderately hard for ${\mathrm{𝖠𝖢}}^0$ circuits is to (a) design some distribution over random restrictions or random projections, (b) show that ${\mathrm{𝖠𝖢}}^0$ circuits simplify to shallow decision trees under these restrictions/projections, and finally (c) show that after applying the restriction/projection, $h$ is moderately hard for shallow decision trees with respect to an appropriate distribution. We show that (roughly speaking) if $h$ can be proven to be moderately hard by a proof with that structure, then XORing multiple copies of $h$ amplifies its hardness. Our analysis involves a new kind of XOR lemma for decision trees, which might be of independent interest.