Difference between revisions of "Open Problems:89"
(Created page with "{{Header |source=focs17 |who=Tom Gur |title=AM vs. NP for proofs of proximity in distribution testing }} ''Proofs of proximity for properties of distributions'' [ChiesaG17]...") |
m (Krzysztof Onak moved page Waiting:Proofs of Proximity, AM vs. MA to Open Problems:89 without leaving a redirect) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
|source=focs17 | |source=focs17 | ||
|who=Tom Gur | |who=Tom Gur | ||
| − | |||
}} | }} | ||
| + | ''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 “$\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. | |
| − | |||
| − | |||
| − | In their basic form, known as | ||
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 14: | Line 11: | ||
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}$ equal to $\mathsf{AM}$ for distribution testing? |
Latest revision as of 16:11, 8 November 2017
| 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?
