Sample-Based Proofs of Proximity

by Guy Goldberg and Guy Rothblum

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:

Available from ECCC TR21-146.

Back to list of Oded's choices.