Computer Science/Discrete Mathematics Seminar II

Why can't we prove tensor rank and Waring rank lower bounds?

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.

Date & Time

February 12, 2019 | 10:30am – 12:30pm

Location

Simonyi Hall 101

Speakers

Visu Makam

Affiliation

University of Michigan; Member, School of Mathematics