Speaker: |
Anamay Tengse |

Organiser: |
Sayantan Chakraborty |

Date: |
Friday, 16 Nov 2018, 16:00 to 17:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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!