Problem 89: AM vs. NP for Proofs of Proximity in Distribution Testing
| Suggested by | Tom Gur |
|---|---|
| Source | FOCS 2017 |
| Short link | https://sublinear.info/89 |
Proofs of proximity for properties of distributions [ChiesaG17] are proof systems within the framework of distribution testing. Since we widely believe that verification is easier than computation (as abstracted in the infamous $\mathsf{P}$ vs. $\mathsf{NP}$ problem), the hope is that using the aid of a proof, or a prover, distribution testing can become significantly easier. Indeed, this turns out to be the case.
In their basic form, known as "$\mathsf{NP}$ distribution testers," a proof-aided tester for a property $\mathcal{P}$ of distributions over domain $\Omega$ is given sample access to a distribution $D$ and explicit access to a proof $\pi$. Given a proximity parameter $\varepsilon>0$, we require that for distributions $D \in \mathcal{P}$, there exists a proof $\pi$ that the tester accepts with high probability, and for distributions $D$ that are $\varepsilon$-far from $\mathcal{P}$ no purported proof $\tilde{\pi}$ will make the tester accept, except with some small probability of error.
More generally, we can consider the notion of interactive proofs for distribution testing. An $\mathsf{AM}$ distribution tester is defined similarly to an $\mathsf{NP}$ tester, however, instead of access to a static proof, the tester is allowed public-coin interaction with an all-powerful, yet untrusted prover.
Surprisingly, while private-coin interactive proofs can help test properties of distributions exponentially more efficient than standard testers, it turns out that both (non-interactive) $\mathsf{NP}$ and $r$-round $\mathsf{AM}$ distribution testers (for any $r$!) can only be quadratically more sample-efficient than standard testers. This means that public-coin interaction can be at most quadratically stronger than non-interactive proofs. But that quadratic upper bound may not be tight, and it it conceivable that these notions are ultimately equivalent in the setting of distribution testing.
Is $\mathsf{NP}=\mathsf{AM}$ for distribution testing?
