# 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* [ChiesaG-17] 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}$ equal to $\mathsf{AM}$ for distribution testing?