BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1638
DTSTAMP:20251112T173923Z
SUMMARY:Factors of Constant-Depth Circuits: Deterministic Algorithms and St
 ructural Bounds
DESCRIPTION:Speaker: Varun Ramanathan (TIFR)\n\nAbstract: \nMultivariate po
 lynomial factorization is a fundamental algebraic problem with connections
  to error-correcting codes\, pseudorandomness and complexity theory. Const
 ant-depth circuits form a restricted yet natural subclass of general polyn
 omial-size arithmetic circuits\, capturing a wide variety of algebraic pro
 blems. In this talk\, we will try and understand some of the ideas that we
 nt into a recent line of work that concluded with a deterministic factoriz
 ation algorithm for constant-depth circuits. More generally\, we will see 
 that for most natural algebraic models\, deterministic (black-box) polynom
 ial identity testing is sufficient for deterministic factorization.At the 
 heart of these algorithmic results\, we will use polynomial identity testi
 ng to project multivariate polynomials to univariate polynomials while pre
 serving information about the factors. The final algorithmic result in thi
 s line of work builds upon a recent surprising and important structural re
 sult: constant-depth circuits (and most natural algebraic models) are clos
 ed under factoring -- if a polynomial has a constant-depth circuit\, then 
 so do its factors.  This talk will be based on collaborations with Somnat
 h Bhattacharjee\, Mrinal Kumar\, Shanthanu Suresh Rai\, Ramprasad Sapthari
 shi\, Shubhangi Saraf and Ben Lee Volk.\n
URL:https://www.tcs.tifr.res.in/web/events/1638
DTSTART;TZID=Asia/Kolkata:20251113T173000
DTEND;TZID=Asia/Kolkata:20251113T183000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR