Open Problems:89 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Proofs of Proximity, AM vs. MA to Open Problems:89 without leaving a redirect

2017-11-08T16:11:27Z

Krzysztof Onak moved page Waiting:Proofs of Proximity, AM vs. MA to Open Problems:89 without leaving a redirect

Krzysztof Onak: Cleaning the header, small changes

2017-11-08T16:11:11Z

Cleaning the header, small changes

Ccanonne at 18:44, 25 October 2017

2017-10-25T18:44:53Z

Ccanonne: 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]..."

2017-10-25T18:43:56Z

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]..."

New page

{{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] 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?

← Older revision		Revision as of 18:44, 25 October 2017
Line 6:		Line 6:


−	''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.	+	''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 "$\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.

← Older revision	Revision as of 16:11, 8 November 2017
(No difference)

@@ Line 2: / Line 2: @@
 |source=focs17
 |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 &ldquo;$\mathsf{NP}$ distribution testers,&rdquo; 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.
@@ 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.
-Is $\mathsf{NP}=\mathsf{AM}$ for distribution testing?
+Is $\mathsf{NP}$ equal to $\mathsf{AM}$ for distribution testing?