Difference between revisions of "Open Problems:89"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Cleaning the header, small changes)
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 "$\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.
  
 
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}=\mathsf{AM}$ for distribution testing?
+
Is $\mathsf{NP}$ equal to $\mathsf{AM}$ for distribution testing?

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?