Speaker: |
Anamay Tengse |

Date: |
Wednesday, 9 Jun 2021, 14:30 to 15:30 |

Venue: |

(Scan to add to calendar)

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