A "Simple" Class of Algebraic Circuits

Anamay Tengse
Sayantan Chakraborty
Friday, 20 Apr 2018, 17:15 to 18:15
A-201 (STCS Seminar Room)
In this talk we will look at $n$-variate polynomials that can be expressed as a small (poly$(n)$) sum of powers of linear polynomials. That is, polynomials that have efficient {\em depth-3-powering} circuits.
We will see an exp$(n)$ lower bound against this model for the {\em monomial} $x_1 x_2 \cdots x_n$, and also an almost matching upper bound using {\em Fischer's trick}. We will then extend the ideas in the lower bound to obtain an $n^{O(\log n)}$ sized hitting set (Forbes-Shpilka '13).
Depending on the time left, we will sketch an $n^{O(\log \log n)}$ sized hitting set construction (Forbes-Shpilka-Saptharishi '14).