Barriers to Lower Bounds in Algebraic Complexity Theory

Project Background

The past few decades have seen a lot of progress in the area of lower bounds in algebraic complexity theory. The main approach to proving lower bounds has been based on an intuition that “computation progresses slowly” in some sense, which we will make precise soon.

This intuition has been captured by the following lower bound template:

1. Define a class of “easy polynomials” $\mathcal{S}$ (for instance, powers of linear forms, or rank-1 tensors). The circuit class will then be characterized by the number of summands of “easy polynomials” that it takes to compute a given polynomial.
2. Devise a linear map $\mathcal{L}$ that maps $\mathcal{S}$ to a class of low-rank matrices $\mathcal{M}$
3. Find a “hard polynomial” $h$ such that $\mathcal{L}(h)$ is a a matrix of high rank.

With the template above, if all easy polynomials (in $\mathcal{S}$) are mapped to matrices of rank at most $r$, and the rank of $\mathcal{L}(h)$ is at least $T$, then (by subadditivity of matrix rank) the circuit computing $h$ must have at least $T/r$ summands of easy polynomials. More explicitly, if $h$ is computed by a circuit of size $s$, then we have $$ h = \sum_{i=1}^s f_i, \quad f_i \in \mathcal{S}$$ which implies (by subadditivity of matrix rank and linearity of $\mathcal{L}$) that $$ T \leq \text{rank}(\mathcal{L}(h)) \leq \sum_{i=1}^s \text{rank}(\mathcal{L}(f_i)) \leq \sum_{i=1}^s r = rs$$ from which the lower bound follows.

The work of EGOW'18 has shown that the above template is not sufficient to prove better lower bounds for the class of diagonal depth 3 circuits as well as for the class of tensors. In particular, the above work shows that no rank methods can prove asymptotically non-trivial lower bounds for border rank of tensors, and that rank methods cannot provide an asymptotically better lower bound than the one obtained by the partial derivative method for diagonal depth 3 circuits.

Project Description

The goal of this project is to understand the limitations of the above template, with the hope that such understanding will guide us to find new ways to prove lower bounds for algebraic complexity classes.

The most important question in this direction is the following:

Question: Can rank methods prove super-polynomial lower bounds for general arithmetic circuits?

By the depth reduction works of Agrawal-Vinay, GKKS'13, and subsequent works, it suffices to answer the above question for homogeneous depth 4 (or even general depth 3) circuits. Thus, the main goal of this project is to understand the limitations of rank methods for proving lower bounds for homogeneous depth 4 circuits.

One particular limitation of the framework proposed by EGOW'18 is that it cannot capture rank methods (such as the shifted partial derivatives) for the class of sums of powers of quadratic polynomials, for which we have exponential lower bounds Kayal'12.

The first goal of this project is to understand how to extend the framework of EGOW'18 to capture rank methods for the class of sums of powers of quadratic polynomials, with a view towards homogeneous depth 4 circuits.

Background Reading

Some useful references for this project are:

• EGOW'18 paper on barriers to rank methods
• CKW'11 survey on partial derivative method in algebraic complexity theory. Also here.
• GKKS'13 paper on depth reduction for arithmetic circuits (and references therein). There has been improvements on this result since then, but this is a good starting point.
• Ramprasad et al’s lower bounds survey and references therein.

Prerequisites

The ideal URA should already have a solid command of:

• linear algebra (equivalent of MATH 245, or MATH 235),
• basic abstract algebra (such as the material from PMATH 347),
• be fairly comfortable writing rigorous proofs.

Having a basic understanding of complexity theory (such as the material from CS 365) is a plus, but not required.

Note: some of the prerequisites can be waived if the student has excellent academic background, such as international olympiads experience, or other similar achievements.

Applying

If you are interested and have the prerequisites for this project, please send me the following by email:

• Transcript
• Resume
• 1-2 paragraphs on why you are interested in this project

Note: any applications deviating significantly from the above instructions will be ignored.