The Communication Complexity of Verifying Distribution PropertiesResearch Paper
An untrusted analyst holds many samples from an unknown distribution over and claims that the distribution has some property: for example, that it is close to uniform or has large support. Interactive proofs for distribution properties (Chiesa–Gur 2018, following Goldwasser–Micali–Rackoff) let a verifier with few samples check such a claim by talking to…