BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1709
DTSTAMP:20260429T055402Z
SUMMARY:Reconstruction of Depth 3 Arithmetic circuits with constant top fan
 -in
DESCRIPTION:Speaker: Devansh Shringi (University of Toronto)\n\nAbstract: \
 nWe consider the problem of reconstructing (exact learning) arithmetic cir
 cuits given blackbox access to evaluations of the polynomial computed by t
 he circuit. This problem is closely connected to central questions in alge
 braic complexity\, including circuit lower bounds\, polynomial identity te
 sting (PIT)\, and tensor decomposition.The focus of the talk will be on de
 pth-3 circuits with bounded top fan-in and on understanding their structur
 e. We study identities computed by such circuits and analyze the set of co
 nstant-codimension subspaces on which these polynomials vanish. These stru
 ctural insights lead to a quasi-polynomial time algorithm for reconstructi
 ng depth-3 circuits with any constant top fan-in. Prior subexponential rec
 onstruction algorithms for this model were known only when the top fan-in 
 is 2 (Sinha '16\, '22) or 3 (Saraf-Shringi '25)\, or when the underlying f
 ield is small (Karnin-Shpilka '09).This talk is based on joint work with S
 hubhangi Saraf and Narmada Varadarajan (https://eccc.weizmann.ac.il/report
 /2025/222/)(to appear in STOC26).\n \nShort Bio : Devansh is a fourth yea
 r PhD student at University of Toronto\, where he works with Shubhangi Sar
 af. Before that he was an undergraduate at IIT Kanpur. His research intere
 sts are in algebraic complexity\, computational complexity\, computational
  algebra \\& number theory and pseudorandomness. \n \n
URL:https://www.tcs.tifr.res.in/web/events/1709
DTSTART;TZID=Asia/Kolkata:20260512T160000
DTEND;TZID=Asia/Kolkata:20260512T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR