License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.5
URN: urn:nbn:de:0030-drops-99044
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9904/
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 epsilon-error probabilistic degree of any Boolean function f:{0,1}^n -> {0,1} over R is the smallest non-negative 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 epsilon-error 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 1-P(bar{x}) is a product of affine forms. We show that the epsilon-error 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:1--5:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-093-4},
ISSN = {1868-8969},
year = {2018},
volume = {122},
editor = {Sumit Ganguly and Paritosh Pandya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9904},
URN = {urn:nbn:de:0030-drops-99044},
doi = {10.4230/LIPIcs.FSTTCS.2018.5},
annote = {Keywords: Polynomials over reals, probabilistic polynomials, probabilistic degree, OR polynomial}
}
|
Keywords: |
|
Polynomials over reals, probabilistic polynomials, probabilistic degree, OR polynomial |
|
Collection: |
|
38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
05.12.2018 |
