Tata Institute of Fundamental Research
Small Hitting Sets for "Tiny" Circuits
STCS Student Seminar
Speaker:
Anamay Tengse
Organiser:
Neha Sangwan
Date:
Friday, 8 Mar 2019, 17:15 to 18:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: For a class of polynomials P, a set of evaluation points H is said to be a hitting set if any nonzero polynomial P is nonzero on some point in H. The problem of constructing _explicit_ hitting sets of "efficient" size for various natural classes of polynomials is a fundamental problem in algebraic complexity theory. However, many seemingly simple variants of this question remain open.
One such case is of the class of polynomials that are sums of powers of linear forms. In the talk we will see a recent result of Forbes, Ghosh and Saxena (ICALP 2018) that gives an explicit construction for poly-sized hitting sets for this model, when the number of variables is tiny (logarithmic in the size). Most arguments in the result are fairly elementary and hence the talk will mostly be self contained.
| Speaker: | Anamay Tengse |
| Organiser: | Neha Sangwan |
| Date: | Friday, 8 Mar 2019, 17:15 to 18:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: For a class of polynomials P, a set of evaluation points H is said to be a hitting set if any nonzero polynomial P is nonzero on some point in H. The problem of constructing _explicit_ hitting sets of "efficient" size for various natural classes of polynomials is a fundamental problem in algebraic complexity theory. However, many seemingly simple variants of this question remain open.
One such case is of the class of polynomials that are sums of powers of linear forms. In the talk we will see a recent result of Forbes, Ghosh and Saxena (ICALP 2018) that gives an explicit construction for poly-sized hitting sets for this model, when the number of variables is tiny (logarithmic in the size). Most arguments in the result are fairly elementary and hence the talk will mostly be self contained.
One such case is of the class of polynomials that are sums of powers of linear forms. In the talk we will see a recent result of Forbes, Ghosh and Saxena (ICALP 2018) that gives an explicit construction for poly-sized hitting sets for this model, when the number of variables is tiny (logarithmic in the size). Most arguments in the result are fairly elementary and hence the talk will mostly be self contained.