BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/899
DTSTAMP:20230914T125942Z
SUMMARY:On the Probabilistic Degree of OR Over The Reals
DESCRIPTION:Speaker: Tulasi mohan Molli\n\nAbstract: \nA probabilistic poly
 nomial is like a randomized algorithm. It is a distribution on polynomial
 s such that\, for each input\, the probabilistic polynomial computes the 
 function exactly with high probability. Probabilistic polynomials seem to
  capture the weakness of constant depth circuits made of AND\, OR and NOT
  gates. In this talk\, we will focus on the probabilistic degree of OR ov
 er the reals.\nClassical results show that the probabilistic degree of OR 
 over reals is at most O(log n * log (1/\\eps)). We will begin by showing 
 a slight improvement of this upper bound to O( (log n - log log (1/\\eps
 )* log(1/\\eps)). It is open if this bound is tight.\nIn all known upper b
 ounds (including the above improvement)\, the polynomials have a special 
 structure: they are essentially product of linear forms. We will show for
  this type of polynomials\, the above upper bound is essentially tight.\n
URL:https://www.tcs.tifr.res.in/web/events/899
DTSTART;TZID=Asia/Kolkata:20180829T171500
DTEND;TZID=Asia/Kolkata:20180829T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR