BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1100
DTSTAMP:20230914T125950Z
SUMMARY:Hitting Sets for Some Algebraic Models - Constructions and Conseque
 nces
DESCRIPTION:Speaker: Anamay Tengse\n\nAbstract: \nWe 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 prob
 lem 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 c
 lass 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 s
 earch of explicit hard polynomials\, finding efficient hitting sets for va
 rious classes of polynomials is a central question in algebraic complexity
  theory.\nOur contributions towards this question are as follows. The firs
 t set of our results extend the scope of known hitting set constructions t
 o other well studied algebraic models. Next\, we show that for any general
  enough algebraic model\, like circuits or formulas\, even a mild improvem
 ent to the trivial hitting sets for the model leads to almost efficient hi
 tting sets for it. Lastly\, we explore how hitting sets for a class of pol
 ynomials can assist us in _proving_ lower bounds against that class.\n
URL:https://www.tcs.tifr.res.in/web/events/1100
DTSTART;TZID=Asia/Kolkata:20201123T111500
DTEND;TZID=Asia/Kolkata:20201123T121500
END:VEVENT
END:VCALENDAR