Algebraic and Analytic Methods in Computational Complexity

Random walks on expanders are extremely useful in TOC. Unfortunately though, they have an inherent cost. E.g., the spectral expansion of a Ramanujan graph deteriorates exponentially with the length of the walk (when compared to a Ramanujan graph of the same degree). In this talk, we will see how this exponential cost can be reduced to linear by applying a permutation after each random step. These permutations are tailor-made to the graph at hand, requiring no randomness. Our proof is established using the powerful framework of finite free probability and interlacing families that was introduced, around ten years ago, by Marcus, Spielman and Srivastava in their seminal works on the existence of bipartite Ramanujan graphs of every size and every degree, and in their solution to the Kadison-Singer problem.

We give a swap-invariant diagonal gate $U_n$ equivalent in constant depth to the $n$-qubit fanout gate. For $t=\pi /4$ and real coupling constants $\{{\alpha }_{i,j}:1\le i,j\le n\}$ with ${\alpha }_{i,j}={\alpha }_{j,i}$, ${\alpha }_{ii}=0$, the Hamiltonian implements $U_n$ (i.e., $U_n=\exp (-i{H}_{\overrightarrow{\alpha }}t)$ up to a global phase factor) if and only if: (1) all the ${\alpha }_{i,j}$ are odd integers; and (2) for all $i$, ${\prod }_{j\ne i}{\alpha }_{i,j}\equiv 1(mod4)$. We give tight constraints on $\{{\alpha }_{i,j}\}$ as above for spatial arrangements of identical qubits satisfying an inverse square law. These constraints are obtained using modular arithmetic on rational numbers.

Joint work with Rabins Wosti.

Let $p$ be an odd prime, $\zeta =e^{2\pi i/p}$ a complex primitive $p^{th}$ root of unity, and $\chi :{\mathbb{Z}}_5\to ℂ$ the quadratic character over ${\mathbb{Z}}_p$. Let $t\in {\mathbb{Z}}_p[x_1,\mathrm{\dots },x_n]$ be an $n$-variable quadratic polynomial ${\sum }_{i,j}{c}_{ij}{x}_i{x}_j+{\sum }_i{\mathrm{\ell }}_i{x}_i$. Consider the exponential sum,

which can be interpreted as the correlation between the parity of the number of $x_i$’s which are quadratic residues and whether $t(𝐱)\equiv 0(p)$. In 2001, Green (JCSS 69, 2004, pp. 28–44) showed that for $p=3$, $|S|\le {(|\zeta --\overline{\zeta }|/2)}^{\lceil n/2\rceil }$, and that this bound can be met by $x_1{x}_2+x_3{x}_4+\mathrm{\dots }$. In this talk, we prove a tight bound for $|S|$ when $p=5$: $|S|\le (|\zeta --\overline{\zeta }|)/2){}^n$, which can be met by the polynomial $x_1^2+x_2^2+\mathrm{\cdots }+x_n^2$. The technique relies on some of the simpler methods of those recently developed by Ivanov, Pavlovic, and Viola (ECCC TR22-092, July 2022). The latter paper consider sums of the form,

again with $t$ quadratic, and, remarkably, prove tight upper bounds met by symmetric polynomials for any complex unit $\zeta$. It is not yet clear how to extend the simpler method for $p=5$ to other odd moduli.

For $n\in \mathbb{N}$ and $d=o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma =2^{-\mathrm{\Theta }(d)}$ such that $F$ can be computed by a uniform depth-$(d+1)$ ${\text{AC}}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed by any depth-$d$ ${\text{TC}}^0$ circuit with $n^{1+\gamma }$ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth $d>2$, which were previously known only for functions outside ${\text{AC}}^0$ such as the parity function. Furthermore, in our result, the ${\text{AC}}^0$ circuit computing $F$ is a monotone read-once formula (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage $n^{-\gamma }$.

Our proof builds on the random projection procedure of Håstad, Rossman, Servedio, and Tan, which they used to prove the celebrated average-case depth hierarchy theorem for ${\text{AC}}^0$ (J. ACM, 2017). We show that under a modified version of their projection procedure, any depth-$d$ threshold circuit with $n^{1+\gamma }$ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth $d+1$ maintains structure.

Since 1995 the functional closure properties of #P are beautifully classified via the coefficients in the expansion over the binomial basis. In order to study the #P (non-)membership of concrete problems related to counting versions of TFNP problems, we start the development of a classification of the #P closure properties on affine varieties. We obtain oracle separations between counting classes, where the existence of the oracle is based on properties of the vanishing ideal of an affine variety, which then translates to a specific polyhedron having no integer point. This is a part of the recent FOCS 2022 paper “What is in #P and what is not”, which is joint work with Igor Pak.

We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomized algorithm for the following problem: If a homogeneous polynomial $f\in K[x_1,\mathrm{\dots },x_n]$ (where $K\subseteq ℂ$) of degree $d$ is given as a blackbox, decide whether it can be written as a linear combination of $d$-th powers of linearly independent complex linear forms. The main novel features of the algorithm are:

• $\mathrm{■}$

  For $d=3$, we improve by a factor of $n$ on the running time from the algorithm in (Koiran and Skomra, 2020). The price to be paid for this improvement is that the algorithm now has two-sided error.

• $\mathrm{■}$

  For $d>3$, we provide the first randomized blackbox algorithm for this problem that runs in time $\text{poly}(n,d)$ (in an algebraic model where only arithmetic operations and equality tests are allowed). Previous algorithms for this problem (Kayal, 2011) as well as most of the existing reconstruction algorithms for other classes appeal to a polynomial factorization subroutine. This requires extraction of complex polynomial roots at unit cost and in standard models such as the unit-cost RAM or the Turing machine this approach does not yield polynomial time algorithms.

• $\mathrm{■}$

  For $d>3$, when $f$ has rational coefficients (i.e. $K=\mathbb{Q}$), the running time of the blackbox algorithm is polynomial in $n,d$ and the maximal bit size of any coefficient of $f$. This yields the first algorithm for this problem over $ℂ$ with polynomial running time in the bit model of computation.

These results are true even when we replace $ℂ$ by $ℝ$. We view the problem as a tensor decomposition problem and use linear algebraic methods such as checking the simultaneous diagonalisability of the slices of a tensor. The number of such slices is exponential in $d$. But surprisingly, we show that after a random change of variables, computing just $3$ special slices is enough. We also show that our approach can be extended to the computation of the actual decomposition. This step relies on matrix diagonalisation which is not an algebraic step over $ℂ$. In forthcoming work we plan to extend these results to overcomplete decompositions, i.e., decompositions in more than $n$ powers of linear forms.

We give 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))$. When we allow unbounded fan-in gates we can get circuits of the same size and depth $O(t(n)/loglogs(n))$.

The determinant of the Vandermonde matrix has a very simple algebraic formula. However, the complexity of its permanent, denoted in this talk as Perm(V), is not known. The permanent of the Vandermonde matrix is a “monomial symmetric polynomial”. In this talk we show that there exist monomial symmetric polynomials that are hard for VNP.

In this talk, I describe some relations between the minimum rank of a decision tree computing a Boolean function and other complexity measures of the function. I also describe a composition theorem in terms of rank and decision tree depth, and show how it simplifies some known lower bounds on decision tree size and rank.

Joint work with Yogesh Dahiya.

In 1893, Sylvester asked a basic question in combinatorial geometry: given a finite set of distinct points $v_1,\mathrm{\dots },v_m\in {ℝ}^N$ such that the line defined by any pair of distinct points $v_i,v_j$ contains a third point $v_k$ in the set, must all points in the set be collinear?

Generalizations of Sylvester’s problem, which are known as Sylvester-Gallai type problems, have found applications in algebraic complexity theory (in Polynomial Identity Testing – PIT) and coding theory (Locally Correctable Codes). The underlying theme in all these types of questions is the following:

Are Sylvester-Gallai type configurations always low-dimensional?

In 2014, Gupta, motivated by such applications in algebraic complexity theory, proposed wide-ranging non-linear generalizations of Sylvester’s question, with applications on the PIT problem.

In this talk, we will discuss these non-linear generalizations of Sylvester’s conjecture, their intrinsic relation to algebraic computation, and a recent theorem proving that radical Sylvester-Gallai configurations for cubic polynomials must have small dimension.

Joint work with Akash Kumar Sengupta.

In this talk I discussed recent joint work with Kevin Pratt on constructing high-dimensional expanders.

Let $\mathrm{\Phi }$ be an irreducible root system (other than $G_2$) of rank at least $2$, let $𝔽$ be a finite field with $p=\mathrm{char}𝔽>3$, and let ${\mathrm{G}}_{\mathrm{\Phi }}𝔽$ be the corresponding Chevalley group. We describe a strongly explicit high-dimensional expander (HDX) family of dimension $\mathrm{rank}(\mathrm{\Phi })$, where ${\mathrm{G}}_{\mathrm{\Phi }}𝔽$ acts simply transitively on the top-dimensional faces; these are $\lambda$-spectral HDXs with $\lambda \to 0$ as $p\to \mathrm{\infty }$. This generalizes a construction of Kaufman and Oppenheim (STOC 2018), which corresponds to the case $\mathrm{\Phi }=A_d$. Our work gives three new families of spectral HDXs of any dimension $\ge 2$, and four exceptional constructions of dimension $4$, $6$, $7$, and $8$.

The celebrated PCP theorem from the 90’s shows that any mathematical proof can be encoded in such a way that its correctness can be verified locally by reading only a tiny number of bits from the encoding.  A fundamental question that has drawn a great amount of interest is what is the minimal overhead in encoding that is needed to allow for such highly efficient local verification. While the original PCP theorem only guarantees a polynomial overhead, a beautiful line of work has culminated in remarkably short encodings with only a poly-logarithmic overhead.   Motivated by cryptographic applications, we study a relatively new interactive variant of PCPs, called Interactive Oracle Proofs, and show that for this model the overhead in the encoding can be made arbitrarily small (approaching 1), and moreover, the prover complexity overhead can be made constant.

The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code.

We propose a new family of sampling tasks such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as “NP not in uniform ACC⁰” and “NP does not have uniform depth-2 threshold circuits”. Indeed, the most general versions of these sampling tasks have implications even for central open problems such as PSPACE vs P and NP vs P.

We observe that these sampling tasks do have non-trivial solutions under standard cryptographic assumptions. Moreover, we can use our framework to capture uniform versions of known non-uniform lower bounds, as well as classical results such as the space hierarchy theorem and Allender’s uniform lower bound for the Permanent. Our framework can also be used to show that NP does not have uniform AC⁰ circuits with a bottom layer of Mod 6 gates – the non-uniform version of this lower bound appears to be an open question.

Border (or approximative) complexity of polynomials plays an integral role in GCT approach to P$\ne$NP. This raises an important open question: can a border circuit be efficiently debordered (i.e. convert from approximative to exact)? Or, could the approximation involve exponential-precision which may not be efficiently simulable? Circuits of depth 3 or 4, are a good testing ground for this question.

Recently, (Kumar ToCT’20) proved the universal power of the border of top-fanin-2 depth-3 circuits. We recently solved some of the related open questions. In this talk we outline our result: border of bounded-top-fanin depth-3 circuits is relatively easy– it can be computed by a polynomial-size algebraic branching program (ABP). Our de-bordering paradigm has many applications, especially in identity testing and lower bounds.

Based on the works with Prateek Dwivedi & Pranjal Dutta (CCC 2021) (FOCS 2021, invited to SICOMP).

The Gaussian correlation inequality (GCI), proved by Royen in 2014, states that any two centrally symmetric convex sets (say K and L) in Gaussian space are positively correlated. We establish a new quantitative version of the GCI which gives a lower bound on this correlation based on the “common influential directions” of K and L. This can be seen as a Gaussian space analogue of Talagrand’s well known correlation inequality for monotone Boolean functions.

To obtain this inequality, we propose a new approach, based on analysis of Littlewood type polynomials, which gives a recipe for transferring qualitative correlation inequalities into quantitative correlation inequalities. En route, we also give a new notion of influences for symmetric convex symmetric sets over Gaussian space which has many of the properties of influences of Boolean functions over the discrete cube. Much remains to be explored about this new notion of influences for convex sets.

Based on joint work with Anindya De and Shivam Nadimpalli.

In 2007 Guruswami, Umans and Vadhan gave an explicit construction of a lossless condenser based on Parvaresh-Vardy codes. This lossless condenser is a fundamental building block in many constructions, and, in particular, is behind state-of-the-art extractor constructions.

We give an alternative construction that is based on Multiplicity codes. While the bottom-line result is similar to the GUV result, the analysis is very different. In GUV (and Parvaresh-Vardy codes) the polynomial ring is closed to a finite field, and every polynomial is associated with related elements in the finite field. In our construction a polynomial from the polynomial ring is associated with its iterated derivatives. Our analysis boils down to solving a differential equation over a finite field, and uses previous techniques, introduced by Kopparty for the list-decoding setting. We also observe that these (and more general) questions were studied in differential algebra, and we use the terminology and result developed there.

We believe these techniques have the potential to get better constructions and solve the current bottlenecks in the area.

Cohn and Umans proposed a group-theoretic approach to bounding the exponent of matrix multiplication. Previous work within this approach ruled out certain families of groups as a route to obtaining $\omega =2$, while other families of groups remain potentially viable. In this work we turn our attention to matrix groups, whose usefulness within this framework was relatively unexplored.

We first show that finite groups of Lie type cannot prove $\omega =2$ within the group-theoretic approach. This is based on a representation-theoretic argument that identifies the second-smallest dimension of an irreducible representation of a group as a key parameter that determines its viability in this framework. Our proof builds on Gowers’ result concerning product-free sets in quasirandom groups. We then give another barrier that rules out certain natural matrix group constructions that make use of subgroups that are far from being self-normalizing.

Our barrier results leave open several natural paths to obtain exponent 2 via matrix groups. To explore these routes we propose working in the continuous setting of Lie groups, in which we develop an analogous theory. Obtaining the analogue of exponent 2 in this potentially easier setting is a key challenge that represents an intermediate goal short of actually proving $\omega =2$. We give constructions in the continuous setting, which evade our two barriers, and indeed are “best-possible” in a precise sense. We then describe a new ingredient – “separating polynomials” – which allow us to recover a full-fledged framework yielding actual algorithms in the Lie setting (rather than constructions whose interest is only by analogy).

A Chor-Goldreich (CG) source is a sequence of random variables where each has min-entropy, even conditioned on the previous ones. We extend this notion in several ways, most notably allowing each random variable to have Shannon entropy conditioned on previous ones. We achieve pseudorandomness results for Shannon-CG sources that were not known to hold even for standard CG sources, and even for the weaker model of Santha-Vazirani sources.

Specifically, we construct a deterministic condenser that on input a Shannon-CG source, outputs a distribution that is close to having constant entropy gap, namely its min-entropy is only an additive constant less than its length. Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders.

Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders) accumulate entropy.