BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1509
DTSTAMP:20250101T115229Z
SUMMARY:Can we proper-learn ROABPs?
DESCRIPTION:Speaker: Anamay Tengse (NISER Bhubaneshwar)\n\nAbstract: \nThe 
 (proper-)learning or reconstruction problem for algebraic computation is t
 he following algorithmic task. Given access to a black box computing a pol
 ynomial F\, output a circuit computing F. It is called "proper-learning'' 
 whenever the output circuit is expected to be of the "same type'' as the p
 rovided black box. This is evidently a harder problem than polynomial iden
 tity testing\, and even designing an efficient\, randomized reconstruction
  algorithm for highly structured circuit-models is a non-trivial task.One 
 such highly structured model is that of Read-once Oblivious ABPs (ROABPs f
 or short)\, where efficient randomized reconstruction is possible\, provid
 ed the algorithm is also given "the order'' of the ROABP\; this is sometim
 es called the "grey-box'' setting. In this talk\, we will explore the miss
 ing part of the question in the title: how hard is it to find the order of
  an ROABP in the black-box setting?Based on a recent work with Vishwas Bha
 rgava\, Pranjal Dutta and Sumanta Ghosh.\n
URL:https://www.tcs.tifr.res.in/web/events/1509
DTSTART;TZID=Asia/Kolkata:20250102T110000
DTEND;TZID=Asia/Kolkata:20250102T120000
LOCATION:A201
END:VEVENT
END:VCALENDAR