Out: Tuesday, 27-Feb
Due: Tuesday, 6-Mar before class
In lecture, we defined \(\mathsf{IP}\), the class of languages that have efficiently verifiable probabilistic interactive proofs. (See Section 10.4 in Sipser to review.) Let us define a closely related class \(\mathsf{IP}_{p,q}\) for two numbers \(0 \leq p,q \leq 1\). A language \(A \subseteq \Sigma^*\) is in \(\mathsf{IP}_{p,q}\) if there exists a polynomial-time verifier \(\mathcal{V}\) (with access to random bits) such that the following holds: \begin{align*} w \in A &\implies \exists \mathcal{P} \ : \ \Pr\left[\mathcal{V} \leftrightarrow \mathcal{P} \textrm{ accepts } w\right] \geq p\,, \\ w \notin A &\implies \forall \mathcal{P} \ : \ \Pr\left[\mathcal{V} \leftrightarrow \mathcal{P} \textrm{ accepts } w\right] \leq q\,. \end{align*} Recall that the probability here is taken over random bits of the verifier. The prover \(\mathcal{P}\) does not use any randomness (since there is no efficiency bound on \(\mathcal{P}\), random bits wouldn't help the prover anyway).
By definition, we have \(\mathsf{IP} := \mathsf{IP}_{\frac23,\frac13}\).
You can use the fact that for every \(0 < p < 1\), if \(X_1, X_2, X_3, \ldots\) are independent flips of a \(p\)-biased coin, then for every \(\varepsilon > 0\), there is a \(k \geq 1\) such that \[ \Pr\left[\frac{1}{k} \left(X_1+\cdots+X_k\right) \in [p-\varepsilon,p+\varepsilon]\right] \geq 1-\varepsilon\,. \]
Suppose that \(A \in \mathsf{IP}\). Thus there is a randomized poly-time verifier \(\mathcal{V}\) such that when \(w \in A\), there is prover \(\mathcal{P}\), and \(\mathcal{V}\) and \(\mathcal{P}\) participate in at most \(h \leq |w|^k\) rounds of interaction after which \(\mathcal{V}\) accepts with probability at least \(2/3\). We can also assume that each message has exactly \(h\) bits. For any \(w\), you will show how to calculate (in polynomimal space) the value \begin{equation*} \max_{\mathcal{P}} \Pr\left[\mathcal{V} \leftrightarrow \mathcal{P} \textrm{ accepts } w \right], \end{equation*} where the maxmium is over all provers \(\mathcal{P}\). Clearly from this value, you can decide whether \(w \in A\), and therefore you will have shown that \(A \in \mathsf{PSPACE}\).
In the interaction between the verifier \(\mathcal{V}\) and the prover \(\mathcal{P}\), let's use \(M_1,M_2,\ldots,M_h\) to denote the messages that \(\mathcal{V}\) sends to \(\mathcal{P}\), and \(m_1,m_2,\ldots,m_h\) for the messages that \(\mathcal{P}\) sends to \(\mathcal{V}\). We can assume that \(\mathcal{V}\) sends the first message and \(\mathcal{P}\) sends the last.
Let's define \(A_w(M_1,M_2,\ldots,M_j; m_1,m_2,\ldots,m_j)\) to be the maximum probability that \(\mathcal{V}\) accepts \(w\), given the interaction so far. In other words, some of the messages are specified, and we look at the maximum acceptance probability over all all provers who send messages \(m_1,m_2,\ldots,m_j\) in the first \(j\) rounds. Show that for \(0 \leq j < h\): \begin{equation}\label{eq:formula}\tag{2} A_w(M_1,\ldots,M_j; m_1,m_2,\ldots,m_j) = \mathbb{E}_{\mathbf{M_{j+1}}}\left[\max_{m_{j+1} \in \{0,1\}^h} A\left(M_1,\ldots,M_j,\mathbf{M}_{j+1}; m_1,m_2,\ldots,m_j,m_{j+1}\right)\right]. \end{equation} Here, we used the notation \(\mathbf{M}_{j+1}\) to denote that the expectation is over the verifier's random choice of the \((j+1)\)st message (given all the messages received so far).