On the probabilistic degree of OR over the reals

We study the probabilistic degree over ℝ of the OR function on n variables. For ε ∈ ( 0 , 1 / 3 ) , the ε ‐error probabilistic degree of any Boolean function f  : {0, 1} n  → {0, 1} over ℝ is the smallest nonnegative integer d such that the following holds: there exists a distribution P of polynomials P ( x 1 , … , x n ) ∈ ℝ [ x 1 , … , x n ] of degree at most d such that for allx ‾ ∈ { 0 , 1 } n, we havePr P ∼ P [ P ( x ‾ ) = f ( x ‾ ) ] ≥ 1 − ε . It is known from the works of Tarui ( Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman ( Proc. 6th CCC 1991), that the ε ‐error probabilistic degree of the OR function is at most O ( log n · log ( 1 / ε ) ) . Our first observation is that this can be improved to O logn ≤ log ( 1 / ε )which is better for small values of ε . In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials P in the support of the distribution P have the following special structure: P ( x 1 , … , x n ) = 1 − ∏ i ∈ [ t ]1 − L i ( x 1 , … , x n ) , where each L i ( x 1 , … ,  x n ) is a linear form in the variables x 1 , … ,  x n , that is, the polynomial 1 − P ( x ‾ ) is a product of affine forms. We show that the ε ‐error probabilistic degree of OR when restricted to polynomials of the above form is Ω logn ≤ log ( 1 / ε )/ log 2logn ≤ log ( 1 / ε ), thus matching the above upper bound (up to poly‐logarithmic factors).