Interactive proofs of proximity for distributions, introduced by Chiesa and Gur (ITCS18) and extensively studied recently by Herman and Rothblum (STOC22, FOCS23, 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.

There was a typo in the original title as well as in the abstract and introduction. These were fixed now.

Interactive proofs of proximity for distributions, introduced by Chiesa and Gur (ITCS18) and extensively studied recently by Herman and Rothblum (STOC22, FOCS23, 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.