Barriers for rank methods in arithmetic complexity


Oct 9, 2017 12:00 AM
Institute for Advanced Study

Arithmetic complexity is considered (for many good reasons) simpler to understand than Boolean complexity. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive.At the same time (and possibly for similar reasons), we have plenty more excuses, in the form of “barrier results” for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Efforts to find barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity.In this talk we will give the first unconditional barriers for rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. In this talk, we will show that:

Rank methods cannot prove better than put bound here lower bound on the tensor rank of any d-dimensional tensor of side n. In particular, they cannot prove super-linear, indeed even >8n tensor rank lower bounds for any 3-dimensional tensors.

Rank methods cannot prove better than BOUND HERE lower bound on the Waring rank of any n-variate polynomial of degree d. In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.

The bounds above nearly match the best explicit bounds we know for these models, and hence offer an explanation why the rank methods got stuck there. Time permitting, we will discuss how these techniques can be extended to barriers for other arithmetic models.

Klim Efremenko
Klim Efremenko
Assistant Professor
Rafael Oliveira
Rafael Oliveira
Assistant Professor of Computer Science

My research interests include complexity theory, algebra, algebraic geometry, commutative algebra, invariant theory, representation theory, derandomization.