Speaker: |
Anamay Tengse |

Organiser: |
Anand Deo |

Date: |
Friday, 12 Oct 2018, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

For the class of n-variate, degree-d polynomials that have algebraic formulas of size s; a hitting set of size poly(n,d,s) is known to exist. However, constructing an explicit hitting set of any non-trivial size remains an open problem. In this talk, we will see the following surprising result. Suppose for some constant $n$ and all $d \leq s$, we have an explicit hitting set of size $s^{(n - 1)}$ for $n$- variate, degree-$d$ polynomials that have formulas of size $s$. Then for all $s$, we have an explicit hitting set of size $s^{tiny(s)}$ for $s$-variate, degree-$s$ polynomials that have formulas of size $s$. Here $tiny(s) = exp(exp(log^{*}s))$, which grows barely faster than a constant. Arguments in the proof will be fairly elementary and hence very little background in algebra or algebraic complexity will be assumed for the talk (joint work with Mrinal Kumar (Simons Institute, UCB) and Ramprasad Saptharishi).