On the probabilistic degree of OR over the reals. Issue 1 (19th January 2021)

• Record Type: Journal Article
• Authors: Bhandari, Siddharth; Harsha, Prahladh; Molli, Tulasimohan; Srinivasan, Srikanth
• Is Part Of: Random structures & algorithms. Volume 59:Issue 1(2021)
• Page Start: 53
• Page End: 67
• Publication Date: 2021-01-19
• Subjects: OR polynomial -- polynomials over reals -- polynomial representations -- probabilistic degree -- probabilistic polynomials; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20991
• Languages: English
• ISSNs: 1042-9832

Abstract

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).