Editing Open Problems:89
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
| Latest revision | Your text | ||
| Line 2: | Line 2: | ||
|source=focs17 | |source=focs17 | ||
|who=Tom Gur | |who=Tom Gur | ||
| + | |title=AM vs. NP for proofs of proximity in distribution testing | ||
}} | }} | ||
| + | |||
| + | |||
''Proofs of proximity for properties of distributions'' {{cite|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. | ''Proofs of proximity for properties of distributions'' {{cite|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 | + | 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. | 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. | ||
| Line 11: | Line 14: | ||
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. | 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} | + | Is $\mathsf{NP}=\mathsf{AM}$ for distribution testing? |
