BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1120
DTSTAMP:20230914T125951Z
SUMMARY:Tensor Rank and Algebraic Formula Lower Bounds
DESCRIPTION:Speaker: Prerona Chatterjee\n\nAbstract: \nTensor are higher d
imensional analogues of matrices and there is a notion of the rank of a te
nsor (similar to matrices). However\, unlike matrices\, finding the rank o
f 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 expli
cit 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 pr
oof 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/relea
ses/download/v8.0.7/fancymain.pdf). Zoom link: https://zoom.us/j/981322275
53?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1120
DTSTART;TZID=Asia/Kolkata:20210312T171500
DTEND;TZID=Asia/Kolkata:20210312T181500
END:VEVENT
END:VCALENDAR