Tata Institute of Fundamental Research
Hitting Sets for Algebraic Models: Constructions and Consequences
PhD Thesis Seminar
Speaker:
Anamay Tengse
Date:
Wednesday, 9 Jun 2021, 14:30 to 15:30
Venue:
(Scan to add to calendar)
Abstract:
We study 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 f from C is zero by querying f on a few points. Formally, H is a hitting set for a class C, if 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 small, explicit hitting sets for various classes of polynomials is a central question in algebraic complexity theory.
Our contributions towards the study of hitting sets are as follows. We provide two explicit constructions of hitting sets: quasipolynomial sized hitting sets for 'UPT circuits', and poly-sized hitting sets for log-variate 'depth-3-powering circuits'. 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, explicit hitting sets for that model. Lastly, we explore how non-trivial hitting sets for a class of polynomials help us in proving lower bounds against that class.
The talk will be based on my joint works with Prerona Chatterjee (TIFR), Mrinal Kumar (IITB), C. Ramya (TIFR) and Ramprasad Saptharishi (TIFR).
Zoom link: https://zoom.us/j/92326426336?pwd=V2h0WGpUeklMd01Mak1sVGpvTm9QUT09
| Speaker: | Anamay Tengse |
| Date: | Wednesday, 9 Jun 2021, 14:30 to 15:30 |
| Venue: |
(Scan to add to calendar)
Abstract:
We study 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 f from C is zero by querying f on a few points. Formally, H is a hitting set for a class C, if 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 small, explicit hitting sets for various classes of polynomials is a central question in algebraic complexity theory.
Our contributions towards the study of hitting sets are as follows. We provide two explicit constructions of hitting sets: quasipolynomial sized hitting sets for 'UPT circuits', and poly-sized hitting sets for log-variate 'depth-3-powering circuits'. 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, explicit hitting sets for that model. Lastly, we explore how non-trivial hitting sets for a class of polynomials help us in proving lower bounds against that class.
The talk will be based on my joint works with Prerona Chatterjee (TIFR), Mrinal Kumar (IITB), C. Ramya (TIFR) and Ramprasad Saptharishi (TIFR).
Zoom link: https://zoom.us/j/92326426336?pwd=V2h0WGpUeklMd01Mak1sVGpvTm9QUT09
Our contributions towards the study of hitting sets are as follows. We provide two explicit constructions of hitting sets: quasipolynomial sized hitting sets for 'UPT circuits', and poly-sized hitting sets for log-variate 'depth-3-powering circuits'. 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, explicit hitting sets for that model. Lastly, we explore how non-trivial hitting sets for a class of polynomials help us in proving lower bounds against that class.
The talk will be based on my joint works with Prerona Chatterjee (TIFR), Mrinal Kumar (IITB), C. Ramya (TIFR) and Ramprasad Saptharishi (TIFR).
Zoom link: https://zoom.us/j/92326426336?pwd=V2h0WGpUeklMd01Mak1sVGpvTm9QUT09