Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROBABILISTIC POLYNOMIAL:
Reports tagged with probabilistic polynomial:
TR21-098 | 7th July 2021
Srikanth Srinivasan, S Venkitesh

#### On the Probabilistic Degree of an $n$-variate Boolean Function

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\to\{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,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 ... more >>>

ISSN 1433-8092 | Imprint