On the Probabilistic Degree of OR Over The Reals

A probabilistic polynomial is like a randomized algorithm. It is a distribution on polynomials such that, for each input, the probabilistic polynomial computes the function exactly with high probability. Probabilistic polynomials seem to capture the weakness of constant depth circuits made of AND, OR and NOT gates. In this talk, we will focus on the probabilistic degree of OR over the reals.

Classical results show that the probabilistic degree of OR over reals is at most O(log n * log (1/\eps)). We will begin by showing a slight improvement of this upper bound to O( (log n - log log (1/\eps)* log(1/\eps)). It is open if this bound is tight.

In all known upper bounds (including the above improvement), the polynomials have a special structure: they are essentially product of linear forms. We will show for this type of polynomials, the above upper bound is essentially tight.