MAJORITY and Probability Amplification

16 November 2023

Given any complexity class \[\mathsf{C}\], the ``random certificates with bounded two-sided error'' operator \[\mathsf{BP}\] is defined as follows: A language \[L \in \mathsf{BP} \cdot \mathsf{C}\] if and only if there exists a polynomial \[p\] and a language \[V \in \mathsf{C}\] such that for all \[x \in \Sigma^*\],

• \[x \in L \implies Pr_r[(x,r) \in V] \geq 3/4\]

• \[x \not\in L \implies Pr_r[(x,r) \not\in V] \geq 3/4\]

Here, it is assumed that \[r \in \Sigma^{p(|x|)}\] is drawn uniformly.

An obvious quirk of this definition is the 3/4, and this really bothered me the first time I ever came across the definitions of \[\mathsf{BPP}\] and \[\mathsf{BQP}\]. Of course, I now know that for \[\mathsf{BPP}\] and \[\mathsf{BQP}\] the 3/4 (or sometimes 2/3) bounds are totally incidental, in the sense that there can be boosted to \[1 - 2^{-t(n)}\] for any polynomial \[t\]. This follows by basically taking a majority vote and applying the Chernoff bound.

A similar thing is true more generally for the class \[\mathsf{BP} \cdot \mathsf{C}\]. In particular, if \[\mathsf{C}\] is closed under (polynomial) majority reductions, then it follows that probability amplification is possible in \[\mathsf{BP} \cdot \mathsf{C}\].

Probability amplification, by the way, is formally defined as follows: A class \[\mathsf{BP} \cdot \mathsf{C}\] admits of probability amplification if and only if for all polynomials \[t\], there is a polynomial \[p\] such that for all \[x \in \Sigma^*\]:

• \[x \in L \implies Pr_r[(x,r) \in V] \geq 1 - 2^{-t(|x|)}\]

• \[x \not\in L \implies Pr_r[(x,r) \not\in V] \geq 1 - 2^{-t(|x|)}\],

where \[r \in \Sigma^{p(|x|)}\] is drawn uniformly.

The easily provable claim, then, is that if \[\mathsf{C}\] is closed under majority reductions, then \[\mathsf{BP} \cdot \mathsf{C}\] admits of probability amplification.

Now, what is interesting about this is if the MAJORITY function is all that essential here. Is it necessary that \[\mathsf{C}\] be able to compute MAJORITY (in the sense of being closed under majority reductions) in order for \[\mathsf{BP} \cdot \mathsf{C}\] to admit of probability amplification?

I find it really interesting that the answer is, in fact, no. The counterexample is \[\mathsf{BP} \cdot \mathsf{AC}^0\]. \[\mathsf{AC}^0\] can't compute MAJORITY, but yet it is known that \[\mathsf{BP} \cdot \mathsf{AC}^0 = \mathsf{AC}^0\]. Therefore, the randomness does nothing for you in \[\mathsf{AC}^0\]. In particular, \[\mathsf{BP} \cdot \mathsf{AC}^0 = \mathsf{AC}^0\] implies \[\mathsf{BP} \cdot \mathsf{AC}^0\] admits of probability amplification, because the probabilities can be made unity.

This begs the question whether a class \[\mathsf{BP} \cdot \mathsf{C}\] admits of probability amplification if and only if either

• \[\mathsf{BP} \cdot \mathsf{C} = \mathsf{C}\] (i.e., there is a way to derandomize \[\mathsf{BP} \cdot \mathsf{C}\])

• or \[\mathsf{C}\] is closed under majority reductions.

Excited to think about this a bit more! If you see a counterexample, then please let me know.