Why can't we prove tensor rank and Waring rank lower bounds?
Presenter
February 12, 2019
Abstract
One of the major goals of complexity theory is to prove lower bounds for various models of computation. The theory often proceeds in buckets of three steps. The first is to come up with a collection of techniques. The second is to be frustrated at the fact that the collection does not seem powerful enough to prove the lower bounds we want. The final step is to prove a âbarrierâ result on the collection of techniques, giving a formal rigorous explanation as to why these techniques do not suffice. Then, of course, one searches for new techniques and the process is repeated. In this talk, I will focus on the problem of tensor rank and Waring rank lower bounds. Most techniques fall under the purview of rank methods. Recently a (suprisingly strong) barrier result has been proven for these methods by Efremenko, Garg, Oliveira and Wigderson. I will explain a complete proof of this result. No special background beyond standard linear algebra will be assumed.