We present two results for computational models that allow error probabilities close to 1/2. First, most computational complexity classes have an analogous class in communication complexity. The class PP in fact has \emph{two}, a version with weakly restricted bias called PP$\cc$, and a version with unrestricted bias called UPP$\cc$. Ever since their introduction by Babai, Frankl, and Simon in 1986, it has been open whether these classes are the same. We show that PP$\cc$ $\subsetneq$ UPP$\cc$. Our proof combines a query complexity separation due to Beigel with a technique of Razborov that translates the acceptance probability of \emph{quantum} protocols to polynomials. Second, we study how small the bias of minimal-degree polynomials that sign-represent Boolean functions needs to be. We show that the worst-case bias is at worst double-exponentially small in the sign-degree (which was very recently shown to be optimal by Podolski), while the average-case bias can be made single-exponentially small in the sign-degree (which we show to be close to optimal).

P.B. Miltersen
Quantum Information Processing , Quantum Computing: algorithms, proofs and tradeoffs , Qubit Applications
IEEE Conference on Computational Complexity
Quantum Computing and Advanced System Research

Buhrman, H.M, Vereshchagin, N.K, & de Wolf, R.M. (2007). On Computation and Communication with Small Bias. In P.B Miltersen (Ed.), 22nd Annual IEEE Conference on Computational Complexity (pp. 24–32). IEEE.