BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1093
DTSTAMP:20230914T125950Z
SUMMARY:Learning arithmetic circuits in the average case via lower bounds
DESCRIPTION:Speaker: Ankit Garg (Microsoft Research\, Bangalore)\n\nAbstrac
 t: \nThe problem of learning arithmetic circuits is the following: given a
  polynomial as a black box that is promised to have a small arithmetic cir
 cuit computing it\, can we find this arithmetic circuit? This problem is h
 ard in the worst case and so previous works have focused on regimes where 
 the NP-hardness doesn't kick in (e.g. constant top fan-in etc.). We focus 
 on the average case where one assumes certain non-degeneracy assumptions o
 n the circuit (formally these amount to assuming the circuit parameters li
 e outside a certain variety and hence if they are chosen randomly accordin
 g to any reasonable distribution\, the non-degeneracy condition is satisfi
 ed whp). Kayal and Saha gave a meta framework (in a rudimentary form) or d
 esigning these algorithms for circuit classes where we have lower bounds. 
 They carried this out for depth 3 circuits (sums of products of linear for
 ms) and we (in joint work with Kayal and Saha) streamline their meta frame
 work and carry it out for depth 4 powering circuits (sums of powers of low
  degree polynomials). I will talk about the meta framework and then about 
 our specific results. I will also talk about a potential application to le
 arning mixtures of general Gaussians.\nYouTube live: https://www.youtube.c
 om/watch?v=qP1M8jmXnzc\n
URL:https://www.tcs.tifr.res.in/web/events/1093
DTSTART;TZID=Asia/Kolkata:20201020T160000
DTEND;TZID=Asia/Kolkata:20201020T170000
END:VEVENT
END:VCALENDAR