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