Computer Science/Discrete Mathematics Seminar II

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.