On doubly-sublinear interactive proofs for distributions

Webpage for a paper by Oded Goldreich and Guy Rothblum


Abstract

Interactive proofs of proximity for distributions, introduced by Chiesa and Gur ({\em ITCS18}) and extensively studied recently by Herman and Rothblum ({\em STOC22}, {\em FOCS23}, {\em FOCS24}), offer a way of verifying properties of distributions using less samples than required to test these properties. We say that such an interactive proof system is {\sf doubly-sublinear} if the verifier's sample complexity is lower than the sample complexity of testing the property, and the honest-prover's sample complexity is lower than the sample complexity of learning the property. We prove a feasibility result for this notion. Specifically, we present properties of distributions for which the prover's sample complexity is close to the complexity of testing, whereas the sample complexity of the verifier is much lower.

Material available on-line


Back to either Oded Goldreich's homepage or general list of papers.