Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SRIKANTH SRINIVASAN:
All reports by Author Srikanth Srinivasan:

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