Premium
On the probabilistic degree of OR over the reals
Author(s) -
Bhandari Siddharth,
Harsha Prahladh,
Molli Tulasimohan,
Srinivasan Srikanth
Publication year - 2021
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20991
Subject(s) - degree (music) , mathematics , probabilistic logic , combinatorics , integer (computer science) , logarithm , polynomial , function (biology) , discrete mathematics , matching (statistics) , affine transformation , product (mathematics) , distribution (mathematics) , statistics , pure mathematics , computer science , mathematical analysis , physics , geometry , evolutionary biology , acoustics , biology , programming language
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).