Fall 2018

Barriers for Rank Methods in Arithmetic Complexity

Thursday, Dec. 6, 2018 2:30 pm3:15 pm PST

Add to Calendar


Klim Efremenko (Ben Gurion University)

In this talk we discuss rank methods lower bounds for arithmetic circuits, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. We will show barriers to these methods. In particular, 1) Rank methods cannot prove better than \Omega_d (n^{\lfloor d/2 \rfloor}) lower bound on the tensor rank of any d-dimensional tensor of side n. (In particular, they cannot prove super-linear, indeed even >6n tensor rank lower bounds for {\em any} 3-dimensional tensors.) 2) Rank methods cannot prove $\Omega_d (n^{\lfloor d/2 \rfloor})$ on the Waring rank of any n-variate polynomial of degree d. This limitations also suggest new ideas how to look for a new rank methods that could be useful for other models.