Bhandari, Siddharth ;
Harsha, Prahladh ;
Molli, Tulasimohan ;
Srinivasan, Srikanth
On the Probabilistic Degree of OR over the Reals
Abstract
We study the probabilistic degree over R of the OR function on n variables. For epsilon in (0,1/3), the epsilonerror probabilistic degree of any Boolean function f:{0,1}^n > {0,1} over R is the smallest nonnegative integer d such that the following holds: there exists a distribution of polynomials Pol in R[x_1,...,x_n] entirely supported on polynomials of degree at most d such that for all z in {0,1}^n, we have Pr_{P ~ Pol}[P(z) = f(z)] >= 1 epsilon. It is known from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that the epsilonerror probabilistic degree of the OR function is at most O(log n * log(1/epsilon)). Our first observation is that this can be improved to O{log (n atop <= log(1/epsilon))}, which is better for small values of epsilon.
In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials P in the support of the distribution Pol have the following special structure: P(x_1,...,x_n) = 1  prod_{i in [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, i.e., the polynomial 1P(bar{x}) is a product of affine forms. We show that the epsilonerror probabilistic degree of OR when restricted to polynomials of the above form is Omega(log (n over <= log(1/epsilon))/log^2 (log (n over <= log(1/epsilon))})), thus matching the above upper bound (up to polylogarithmic factors).
BibTeX  Entry
@InProceedings{bhandari_et_al:LIPIcs:2018:9904,
author = {Siddharth Bhandari and Prahladh Harsha and Tulasimohan Molli and Srikanth Srinivasan},
title = {{On the Probabilistic Degree of OR over the Reals}},
booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
pages = {5:15:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770934},
ISSN = {18688969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9904},
URN = {urn:nbn:de:0030drops99044},
doi = {10.4230/LIPIcs.FSTTCS.2018.5},
annote = {Keywords: Polynomials over reals, probabilistic polynomials, probabilistic degree, OR polynomial}
}
05.12.2018
Keywords: 

Polynomials over reals, probabilistic polynomials, probabilistic degree, OR polynomial 
Seminar: 

38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Issue date: 

2018 
Date of publication: 

05.12.2018 