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 -u003e {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)] u003e= 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 u003c= 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 u003c= log(1/epsilon))/log^2 (log (n over u003c= log(1/epsilon))})), thus matching the above upper bound (up to polylogarithmic factors). |
Year | DOI | Venue |
---|---|---|
2018 | 10.4230/LIPIcs.FSTTCS.2018.5 | FSTTCS |
DocType | Volume | ISSN |
Journal | abs/1812.01982 | In Proc. 38th IARCS Conf. on Foundations of Software Technology &
Theoretical Computer Science (FSTTCS) (Ahmedabad, India, 10-14 December),
volume 122 of LiPiCS, pages 5:1-5:12, 2018 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Siddharth Bhandari | 1 | 0 | 3.04 |
Prahladh Harsha | 2 | 371 | 32.06 |
Tulasimohan Molli | 3 | 0 | 0.68 |
Srikanth Srinivasan | 4 | 132 | 21.31 |