Abstract
Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}ⁿ → {0,1} that depends on all its input variables, when represented as a realvalued multivariate polynomial P(x₁,…,x_n), has degree at least log n  O(log log n). This was improved to a tight (log n  O(1)) bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)).
In this paper, we address this question for Probabilistic degree. The function f has probabilistic degree at most d if there is a random realvalued polynomial of degree at most d that agrees with f at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the bestknown bounds put it between (log n)^{1/2o(1)} and O(log n) (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)).
Here we can give a nearoptimal understanding of the probabilistic degree of nvariate functions f, 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 such an f is at least (log n)^{c/(c+1)o(1)}, and we show this is tight up to (log n)^{o(1)} factors.
BibTeX  Entry
@InProceedings{srinivasan_et_al:LIPIcs.APPROX/RANDOM.2021.42,
author = {Srinivasan, Srikanth and Venkitesh, S.},
title = {{On the Probabilistic Degree of an nVariate Boolean Function}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {42:142:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14735},
URN = {urn:nbn:de:0030drops147356},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.42},
annote = {Keywords: truly nvariate, Boolean function, probabilistic polynomial, probabilistic degree}
}
Keywords: 

truly nvariate, Boolean function, probabilistic polynomial, probabilistic degree 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) 
Issue Date: 

2021 
Date of publication: 

15.09.2021 