On the Probabilistic Degree of OR over the Reals
share
We study the probabilistic degree over reals of the OR function on n variables. For an error parameter ϵ in (0,1/3), the ϵ-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 entirely supported on polynomials of degree at most d such that for all z ∈{0,1}^n, we have Pr_P ∼ D [P(z) = f(z) ] ≥ 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( n. 1/ϵ). Our first observation is that this can be improved to On≤ 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 D have the following special structure:P = 1 - (1-L_1).(1-L_2)...(1-L_t), where each L_i(x_1,..., x_n) is a linear form in the variables x_1,...,x_n, i.e., the polynomial 1-P(x_1,...,x_n) is a product of affine forms. We show that the ϵ-error probabilistic degree of OR when restricted to polynomials of the above form is Ω ( a/^2 a ) where a = n≤ 1/ϵ. Thus matching the above upper bound (up to poly-logarithmic factors).
READ FULL TEXT