Tata Institute of Fundamental Research
Tensor Rank and Algebraic Formula Lower Bounds
STCS Student Seminar
Speaker:
Prerona Chatterjee
Organiser:
Neha Sangwan
Date:
Friday, 12 Mar 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
Abstract:
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/fancymain.pdf). Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
| Speaker: | Prerona Chatterjee |
| Organiser: | Neha Sangwan |
| Date: | Friday, 12 Mar 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
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/fancymain.pdf). Zoom link: https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09