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