Location-Invariant Properties of Functions Versus Properties of Distributions: United in Testing but Separated in Verification

Authors Oded Goldreich† and Guy N. Rothblum

A property of functions is called location-invariant (or symmetric) if it can be characterized in terms of the frequencies with which each value occurs in the function, regardless of the locations at which each value occurs. It is known that the query complexity of testing location-invariant properties of functions is closely related to the sample complexity of testing the corresponding distributions. The main message of this work is that this close relationship does not hold in the context of verification. This remains true whether considering verification via general interactive proofs of proximity (i.e., IPPs) or restricting attention to doubly-sublinear IPPs (ds-IPPs). Alternatively, one may view this work as a subsequent step in the study of doubly-sublinear IPPs for properties of functions, where we say that an IPP is doubly-sublinear if: (1) the query complexity of the verifier is sublinear in the query complexity of testing the property, and (2) the query complexity of the honest prover is sublinear in the query complexity of learning a function with that property. Specifically, we present doubly-sublinear IPPs for several natural location-invariant properties. Our results include: (1) We present doubly-sublinear IPPs for the set of functions from [m] to [n] in which each value occurs m/n times: For every α ∈ (0, 0.5), the query complexity of the verifier is O(n^{0.5−α}), and the query complexity of the honest prover is e^{O(n^{0.5+α}/ε^2)}. (2) We present doubly-sublinear IPPs for the set of functions from [m] to [n] in which each value occurs either m/k times or not at all: For every α ∈ (0, 1/3), the query complexity of the verifier is poly(1/ε) · k^{(2/3)−2α}, and the query complexity of the prover is poly(1/ε) · e^{O(k^{(2/3)+α})}. In contrast, in both cases, it is known that the corresponding properties of distributions have no doubly-efficient IPP (see Herman and Rothblum, 2025). Actually, the first property of distributions (i.e., uniformity over [n]) does not even admit an IPP in which the verifier uses o(n^{1/2}) samples, regardless of other complexity measures.

Related readings and updates.

Suppose Alice has collected a small number of samples from an unknown distribution and would like to learn about it. Bob, an untrusted data analyst, claims to have run sophisticated analysis on the distribution and makes assertions about its properties. When and how is it possible for Alice to efficiently verify Bob's claims (using fewer resources than would be needed to run the analysis herself)? We construct interactive...

As statistical analyses become more central to science, industry, and society, there is a growing need to ensure the correctness of their results. Approximate correctness can be verified by replicating the entire analysis, but can we verify without replication? Building on recent work, we study proof systems that allow a probabilistic verifier to ascertain that the results of an analysis are approximately correct while drawing fewer samples...