Tensor Rank and Algebraic Formula Lower Bounds



Friday, 12 March 2021, 17:15 to 18:15


Tensor are higher dimensional analogues of matrices and there is a notion of the rank of a tensor (similar to matrices). However, unlike matrices, finding the rank of a tensor is NP-hard and it is a big open problem to find explicit tensor of large rank. Raz showed that in certain regimes, finding such an explicit tensor would yield lower bounds against algebraic formulas (a natural model for computing polynomials). In this talk, we will introduce tensors and view them as some structured polynomials. We will then go over the proof idea of the statement mentioned above and completely prove one of the main structural lemmas used. The talk is based on the presentation of Raz's paper (https://dl.acm.org/doi/10.1145/2535928) as given in chapter 16 of Ramprasad's survey (https://github.com/dasarpmar/lowerbounds-survey/releases/download/v8.0.7...). Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09