Tata Institute of Fundamental Research
Hitting Sets for Some Algebraic Models - Constructions and Consequences
PhD Synopsis Seminar
Speaker:
Anamay Tengse
Organiser:
Ramprasad Saptharishi
Date:
Monday, 23 Nov 2020, 11:15 to 12:15
Venue:
(Scan to add to calendar)
Abstract:
We study the question of constructing _hitting sets_ for polynomials computed by several algebraic models. For a class of polynomials C, hitting sets for C capture the problem of _deterministic_ blackbox PIT for C - checking if a polynomial from C is zero by querying it on a few points. Formally, a hitting set for a class C is a set H such that for every nonzero f in C, there is some point h in H for which f(h) is nonzero. Owing to its close connections to the search of explicit hard polynomials, finding efficient hitting sets for various classes of polynomials is a central question in algebraic complexity theory.
Our contributions towards this question are as follows. The first set of our results extend the scope of known hitting set constructions to other well studied algebraic models. Next, we show that for any general enough algebraic model, like circuits or formulas, even a mild improvement to the trivial hitting sets for the model leads to almost efficient hitting sets for it. Lastly, we explore how hitting sets for a class of polynomials can assist us in _proving_ lower bounds against that class.
| Speaker: | Anamay Tengse |
| Organiser: | Ramprasad Saptharishi |
| Date: | Monday, 23 Nov 2020, 11:15 to 12:15 |
| Venue: |
(Scan to add to calendar)
Abstract:
We study the question of constructing _hitting sets_ for polynomials computed by several algebraic models. For a class of polynomials C, hitting sets for C capture the problem of _deterministic_ blackbox PIT for C - checking if a polynomial from C is zero by querying it on a few points. Formally, a hitting set for a class C is a set H such that for every nonzero f in C, there is some point h in H for which f(h) is nonzero. Owing to its close connections to the search of explicit hard polynomials, finding efficient hitting sets for various classes of polynomials is a central question in algebraic complexity theory.
Our contributions towards this question are as follows. The first set of our results extend the scope of known hitting set constructions to other well studied algebraic models. Next, we show that for any general enough algebraic model, like circuits or formulas, even a mild improvement to the trivial hitting sets for the model leads to almost efficient hitting sets for it. Lastly, we explore how hitting sets for a class of polynomials can assist us in _proving_ lower bounds against that class.
Our contributions towards this question are as follows. The first set of our results extend the scope of known hitting set constructions to other well studied algebraic models. Next, we show that for any general enough algebraic model, like circuits or formulas, even a mild improvement to the trivial hitting sets for the model leads to almost efficient hitting sets for it. Lastly, we explore how hitting sets for a class of polynomials can assist us in _proving_ lower bounds against that class.