Name
Abstract | ||
|---|---|---|
We study the probabilistic degree over R of the OR function on n variables. For epsilon is an element of(0,1/3), the epsilon-error 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 P of polynomials P(x(1,) ..., x(n), ,x(n))is an element of R[x(1),...,x(n)] of degree at most d such that for all (x) over bar is an element of{0,1}(n), we have Pr-P similar to P[P((x) over bar = >= 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(<= log(1/epsilon(n))) 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 P have the following special structure: P(x(1),., x(n)) = 1 - Pi(i is an element of[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,., xn, that is, the polynomial 1 - P((x) over bar) 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 (<= log(1/epsilon)/log(2) (log (log ((n)(<= log(1/epsilon))))), thus matching the the above upper bound (up to poly-logarithmic factors). |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1002/rsa.20991 | RANDOM STRUCTURES & ALGORITHMS |
Keywords | DocType | Volume |
OR polynomial, polynomials over reals, polynomial representations, probabilistic degree, probabilistic polynomials | Journal | 59 |
Issue | ISSN | Citations |
1 | 1042-9832 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Siddharth Bhandari | 1 | 0 | 3.04 |
| Prahladh Harsha | 2 | 0 | 0.34 |
| Tulasimohan Molli | 3 | 0 | 0.34 |
| Srikanth Srinivasan | 4 | 0 | 1.01 |