Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>