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

Details

This paper from Oded Goldreich and Guy Rothblum (Weizmann Institute / Apple ML Research) investigates a known testing equivalence: location-invariant function properties (where only value frequencies matter, not positions) mirror corresponding distribution properties in query/sample complexity. The paper's main result is that this equivalence breaks completely in the verification setting. When interactive proofs are added — either general IPPs or the stricter doubly-sublinear variant — function properties and distribution properties become fundamentally different in complexity. The authors demonstrate doubly-sublinear IPPs for two concrete symmetric function properties: (1) uniform distribution over [n], where verifier complexity is O(n^{0.5−α}) for any α in (0, 0.5), and (2) functions where each value appears exactly m/k times, with verifier complexity poly(1/ε)·k^{(2/3)−2α}. The key contrast: the corresponding distribution properties (including plain uniformity testing over n elements) provably have no IPP where the verifier uses o(n^{1/2}) samples, regardless of other complexity measures. Same problem structure, same testing complexity, completely different verification complexity. This is a narrow theoretical separation result within the IPP complexity framework, part of a cluster of Apple/Weizmann papers at FOCS/ITCS 2026. Limited near-term practical impact but relevant to researchers building verified statistical systems.