Abstract: 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 for $M_i$s. It was shown by Levitzki in 1950 that any identity for $m \times m$ matrices has to have a degree of at least $2m$. The \emph{Amitsur-Levitzki theorem} then provided an identity of degree $2m$ for $m \times m$ matrices for all $m$.
In 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 if $f$ is a polynomial with $t$ monomials, then it cannot be an identity for $m \times m$ matrices, whenever $m > \log_2{t}$.
P.S. : It is worth mentioning that the proof involves an elegant use of nondeterministic automata!
