8:00am 


9:00am 


10:00am 


11:00am 


12:00pm 


1:00pm 


2:00pm 
[2:30pm] S. Venkitesh, IIT Bombay
 Description:
 Title: On the Probabilistic Degree of an nvariate Boolean Function
Speaker: S. Venkitesh
DayDate: Tuesday, July 27, 2021
Time: 14:30  15:30 hrs IST
Google Meet link: https://meet.google.com/qixcatfkqy
Abstract: Consider the following question: Let f : {0,1}^n \to {0,1} be a
Boolean function that depends on all its input variables. (We call such a
function `truly nvariate'.) What is the least degree of a realvalued
multivariate polynomial P(X_1,...,X_n) that represents the function f ?
Nisan and Szegedy (1994) gave the lower bound log n  O(log log n), and
this was improved by Chiarelli, Hatami and Saks (2020) to a tight bound
log n  O(1).
We will explore a probabilistic analog of the above question: Given a
truly nvariate Boolean function f, what is the least degree of a
realvalued `random' polynomial that agrees with f, with high
probability, at every input? This least degree is called the
`probabilistic degree' of f, and is an important complexity measure for
Boolean functions. Our understanding of this complexity measure is
quite weak. For instance, we don't even know the probabilistic degree
of the OR function (which takes the value 0 at the all0s input, and 1
at every other input). The bestknown bounds put it between (log
n)^{1/2  o(1)} and O(log n).
In this talk, we will give a nearoptimal understanding of the
probabilistic degree of truly nvariate Boolean functions, modulo our
lack of understanding of the probabilistic degree of OR. We show that
if the probabilistic degree of OR is (log n)^c, then the minimum
possible probabilistic degree of a truly nvariate Boolean function is
at least (log n)^{c/(c+1)  o(1)}, and this bound is tight up to (log
n)^{o(1)} factors.
This is a joint work with Srikanth Srinivasan.
(https://eccc.weizmann.ac.il/report/2021/098/).


3:00pm 

4:00pm 


5:00pm 


6:00pm 

