BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/916
DTSTAMP:20230914T125943Z
SUMMARY:Sparsity Bound for Matrix Identities
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nAbstract: A polynomial $
 f(x_1\,\\ldots\,x_n)$ is said to be an identity for $m \\times m$ matrices
  if $f(M_1\,\\ldots\,M_n) = 0$ for all choices of $m \\times m$ matrices f
 or $M_i$s. It was shown by Levitzki in 1950 that any identity for $m \\tim
 es m$ matrices has to have a degree of at least $2m$. The \\emph{Amitsur-L
 evitzki theorem} then provided an identity of degree $2m$ for $m \\times m
 $ matrices for all $m$.\nIn this talk\, we will see a bound on the number 
 of monomials (sparsity) of an identity for $m \\times m$ matrices\, due to
  Arvind\, Joglekar\, Mukhopadhyay and Raja (STOC 2017). They showed that i
 f $f$ is a polynomial with $t$ monomials\, then it cannot be an identity f
 or $m \\times m$ matrices\, whenever $m > \\log_2{t}$.\nP.S. : It is worth
  mentioning that the proof involves an elegant use of nondeterministic aut
 omata!\n
URL:https://www.tcs.tifr.res.in/web/events/916
DTSTART;TZID=Asia/Kolkata:20181116T160000
DTEND;TZID=Asia/Kolkata:20181116T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR