On the probabilistic degree of OR over the reals
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan · Random Structures and Algorithms · 2021
Abstract We study the probabilistic degree over of the OR function on n variables. For , 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 of degree at most d such that for all , we have . 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 . Our first observation is that this can be improved to 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: where each Li(x1, … , xn) is a linear form in the variables x1, … , xn, that is, the polynomial is a product of affine forms. We show that the ‐error probabilistic degree of OR when restricted to polynomials of the above form is , thus matching the above upper bound (up to poly‐logarithmic factors).