Testing Distributions of Huge Objects
summary
Defines the DOHO model—sampling distributions over length-n strings with queries to sampled bits and distance measured by the earthmover's distance under normalized Hamming—and proves the main claim: if a distribution property is closed under arbitrary mappings then the query complexity is about the standard sample complexity times 1/epsilon (up to polylog factors). The construction picks a random index subset, restricts samples to it and runs a standard tester; random restriction and collision-statistics are the key tools. Applications: support-size m needs Θ(m) queries, and uniform-over-m-set testing admits query bounds far below the usual m^{2/3} sample barrier.
AI-written summary · about