Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-138 | 6th October 2019 18:40

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

TR19-138
Authors: Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh
Publication: 6th October 2019 18:42
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 of Boolean functions --- specifically symmetric Boolean functions --- have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems.