Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROBABILISTIC DEGREE:
Reports tagged with Probabilistic degree:
TR19-138 | 6th October 2019
Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

#### On the Probabilistic Degrees of Symmetric Boolean functions

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>

ISSN 1433-8092 | Imprint