Mathematics

Dr. Arpita Korwar
IIT Kanpur

In computational complexity, arithmetic circuits are used to
compactly represent polynomials. How 'difficult' a polynomial is can be
measured by looking at the 'easiest' arithmetic circuit that represents
that polynomial. A Polynomial Identity Test for a family of circuits takes
a circuit from that family and says whether the polynomial computed by
that circuit is identically zero or not.

In this talk, we will look at special arithmetic circuits called
Arithmetic Branching Programs. They compute polynomials that can be
written as an Iterated Matrix Multiplication. We will give a
quasi-polynomial time hitting set for the sum of ROABPs. In the process,
we will study some defining properties of ROABPs.