A "Simple" Class of Algebraic Circuits

Speaker: 

Time: 

Friday, 20 April 2018, 17:15 to 18:15

Venue: 

Organisers: 

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).