Description

Title: On the Probabilistic Degree of an n-variate Boolean Function

Speaker: S. Venkitesh

Day-Date: Tuesday, July 27, 2021

Time: 14:30 - 15:30 hrs IST

Google Meet link: https://meet.google.com/qix-catf-kqy

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 n-variate'.) What is the least degree of a real-valued

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 n-variate Boolean function f, what is the least degree of a

real-valued `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 all-0s input, and 1

at every other input). The best-known bounds put it between (log

n)^{1/2 - o(1)} and O(log n).

In this talk, we will give a near-optimal understanding of the

probabilistic degree of truly n-variate 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 n-variate 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/).

Speaker: S. Venkitesh

Day-Date: Tuesday, July 27, 2021

Time: 14:30 - 15:30 hrs IST

Google Meet link: https://meet.google.com/qix-catf-kqy

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 n-variate'.) What is the least degree of a real-valued

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 n-variate Boolean function f, what is the least degree of a

real-valued `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 all-0s input, and 1

at every other input). The best-known bounds put it between (log

n)^{1/2 - o(1)} and O(log n).

In this talk, we will give a near-optimal understanding of the

probabilistic degree of truly n-variate 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 n-variate 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/).

Date

Tue, July 27, 2021

Start Time

2:30pm-3:30pm IST

Duration

1 hour

Priority

5-Medium

Access

Public

Created by

DEFAULT ADMINISTRATOR

Updated

Sun, July 25, 2021 10:53pm IST