On the probabilistic degree of OR over the reals. Issue 1 (19th January 2021) - Bhandari, Siddharth; Harsha, Prahladh; Molli, Tulasimohan; Srinivasan, Srikanth
Abstract: 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 all x ‾ ∈ 0, 1 n, we have Pr 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 log n ≤ 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 Ω log n ≤ log ( 1 / ε ) / log 2 log n ≤ log ( 1 / ε ), thus matching the above upper bound (up to poly‐logarithmic factors).