## Proofs of Proximity for Distribution Testing

by Alessandro Chiesa and Tom Gur

#### Oded's comments

This paper introduces the notions of non-interactive and interactive proofs
of proximity for properties of distributions, and initiates their study.
These notions were studied before in the context of properties
of functions, but the two settings are fundamentally different,
and this fact is farther demonstrated by the results of this paper.
The results are very informative and intriguing,
and include the fact that non-interactive proofs do not offer
more than a quadratic saving in complexity (which is achievable
in some cases), that interactive proofs can be exponentially
stronger than that, but only if they use private coins.
Indeed, the separation between the power of general interactive
proofs (of proximity for distributions) and their public-coin variants
is the most striking result in this paper.

#### The original abstract

Distribution testing is an area of property testing that studies algorithms
that receive few samples from a probability distribution D and decide
whether D has a certain property or is far (in total variation distance)
from all distributions with that property. Most natural properties of
distributions, however, require a large number of samples to test, which
motivates the question of whether there are natural settings wherein fewer
samples suffice.

We initiate a study of proofs of proximity for properties of distributions.
In their basic form, these proof systems consist of a tester that not only
has sample access to a distribution but also explicit access to a proof
string that depends on the distribution. We refer to these as NP
distribution testers, or MA distribution testers if the tester is a
probabilistic algorithm. We also study the more general notion of IP
distribution testers, in which the tester interacts with an all-powerful
untrusted prover.

We investigate the power and limitations of proofs of proximity for
distributions and chart a landscape that, surprisingly, is significantly
different from that of proofs of proximity for functions. Our main results
include showing that MA distribution testers can be quadratically stronger
than standard distribution testers, but no stronger than that; in contrast,
IP distribution testers can be exponentially stronger than standard
distribution testers, but when restricted to public coins they can be at
best quadratically stronger.

See ECCC TR17-155.

Back to
list of Oded's choices.