Event calendar file
School of Technology and Computer Science Seminars
A "Simple" Class of Algebraic Circuits
by Anamay Tengse (School of Technology and Computer Science, TIFR)
Friday, April 20, 2018
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
| Description |
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).
|
