BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1134
DTSTAMP:20230914T125951Z
SUMMARY:Hitting Sets for Algebraic Models: Constructions and Consequences
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nWe study hitting sets for
polynomials computed by several algebraic models. For a class of polynomi
als C\, hitting sets for C capture the problem of deterministic blackbox P
IT 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 nonzer
o 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 cen
tral question in algebraic complexity theory.\n\nOur contributions towards
the study of hitting sets are as follows. We provide two explicit constru
ctions of hitting sets: quasipolynomial sized hitting sets for 'UPT circui
ts'\, and poly-sized hitting sets for log-variate 'depth-3-powering circui
ts'. Next\, we show that for any general enough algebraic model\, like cir
cuits or formulas\, even a mild improvement to the trivial hitting sets fo
r the model leads to almost efficient\, explicit hitting sets for that mod
el. Lastly\, we explore how non-trivial hitting sets for a class of polyno
mials help us in proving lower bounds against that class.\n\nThe talk will
be based on my joint works with Prerona Chatterjee (TIFR)\, Mrinal Kumar
(IITB)\, C. Ramya (TIFR) and Ramprasad Saptharishi (TIFR).\n\nZoom link: h
ttps://zoom.us/j/92326426336?pwd=V2h0WGpUeklMd01Mak1sVGpvTm9QUT09\n
URL:https://www.tcs.tifr.res.in/web/events/1134
DTSTART;TZID=Asia/Kolkata:20210609T143000
DTEND;TZID=Asia/Kolkata:20210609T153000
END:VEVENT
END:VCALENDAR