Tata Institute of Fundamental Research
A "Simple" Class of Algebraic Circuits
STCS Student Seminar
Speaker:
Anamay Tengse
Organiser:
Sayantan Chakraborty
Date:
Friday, 20 Apr 2018, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Anamay Tengse |
| Organiser: | Sayantan Chakraborty |
| Date: | Friday, 20 Apr 2018, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).