Sample-Based Proofs of Proximity

Oded's comments

I was waiting for a few months to recommend this work, but only noticed now that it was already posted on ECCC in mid-October.

This work introduces an interactive proof of proximity (IPP) version of the notion of sample based (property) testers. I am most excited by the positive results. Specifically, the transformation of a wide class of query-based IPPs (resp., a class of property testers) into sample-based IPPs of sublinear (resp., very low) complexity. These results are couples with indications that the restrictions used in them are actually necessary.

The original abstract

Suppose we have random sampling access to a huge object, such as a graph or a database. Namely, we can observe the values of random locations in the object, say random records in the database or random edges in the graph. We cannot, however, query locations of our choice. Can we verify complex properties of the object using only this restricted sampling access?

In this work, we initiate the study of sample-based proof systems, where the verifier is extremely constrained; Given an input, the verifier can only obtain samples of uniformly random and i.i.d. locations in the input string, together with the values at those locations. The goal is verifying complex properties in sublinear time, using only this restricted access. Following the literature on Property Testing and on Interactive Proofs of Proximity (IPPs), we seek proof systems where the verifier accepts every input that has the property, and with high probability rejects every input that is far from the property.

We study both interactive and non-interactive sample-based proof systems, showing:

• On the positive side, our main result is that rich families of properties / languages have sub-linear sample-based interactive proofs of proximity (SIPPs). We show that every language in NC has a SIPP, where the sample and communication complexities, as well as the verifier's running time, are $\tildeO({\sqrt n})$, and with polylog(n) communication rounds. We also show that every language that can be computed in polynomial-time and bounded-polynomial space has a SIPP, where the sample and communication complexities of the protocol, as well as the verifier's running time are roughly $\sqrt n$, and with a constant number of rounds.
  This is achieved by constructing a reduction protocol from SIPPs to IPPs. With the aid of an untrusted prover, this reduction enables a restricted, sample-based verifier to simulate an execution of a (query-based) IPP, even though it cannot query the input. Applying the reduction to known query-based IPPs yields SIPPs for the families described above.
• We show that every language with an adequate (query-based) property tester has a 1-round SIPP with constant sample complexity and logarithmic communication complexity. One such language is equality testing, for which we give an explicit and simple SIPP.
• On the negative side, we show that interaction can be essential: we prove that there is no non-interactive sample-based proof of proximity for equality testing.
• Finally, we prove that private coins can dramatically increase the power of SIPPs. We show a strong separation between the power of public-coin SIPPs and private-coin SIPPs for Equality Testing.

Available from ECCC TR21-146.