Talks & Seminars
Title: Bootstrapping Identity Tests for Algebraic Circuits
Mr. Anamay Tengse, TIFR, Mumbai
Date & Time: August 1, 2018 14:00
Venue: Room no. 109, 01st Floor, Department of Computer Science and Engineering, New CSE/CC Building
The classical Ore-DeMillo-Lipton-Schwartz-Zippel lemma [O22,DL78,Z79,S80] states that any nonzero polynomial of degree at most $s$ over $n$ variables will evaluate to a nonzero value at some point on a grid $S^n$ with $|S| > s$. This leads to a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ algebraic circuits over $n$ variables that runs in time $poly(s) \cdot (s+1)^n$. Agrawal, Ghosh and Saxena recently introduced the technique of \emph{bootstrapping} that can be used to asymptotically improve the running time of \emph{blackbox} identity tests. They showed that a running time of as bad as $(s+1)^{n^{0.5 - \delta}} H(n)$ for any $\delta > 0$ and arbitrary $H$ can be improved to a running time of $s^{\exp \circ \exp(\log^{\ast} s)}$, which is slightly super-polynomial. Building on their work we show that the hypothesis can be weakened further to a running time of $(s+1)^{o(n)} H(n)$ (slightly better than the trivial $s^{O(n)}$) to get essentially the same conclusion. This is a joint work with Mrinal Kumar (Harvard, Cambridge, MA) and Ramprasad Saptharishi (TIFR, Mumbai).
Speaker Profile:
Details available at http://www.tcs.tifr.res.in/~anamay/.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback