On Computation and Communication with Small Bias

Abstract

Many models in theoretical computer science allow for computations or representations where the answer is only slightly biased in the right direction. The best-known of these is the complexity class PP, for “probabilistic polynomial time”. A language is in PP if there is a randomized polynomial-time Turing machine whose acceptance probability is greater than 1/2 if, and only if, its input is in the language.

Most computational complexity classes have an analogous class in communication complexity. The class PP in fact has two, a version with weakly restricted bias called PPcc, and a version with unrestricted bias called UPPcc. Ever since their introduction by Babai, Frankl, and Simon in 1986, it has been open whether these classes are the same. We show that PPcc is strictly included in UPPcc. Our proof combines a query complexity separation due to Beigel with a technique of Razborov that translates the acceptance probability of quantum protocols to polynomials. We will discuss some complexity theoretical consequences of this separation. This presentation is bases on joined work with Nikolay Vereshchagin and Ronald de Wolf.