2026-07-23T07:57:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21065 2024-09-16T06:02:39Z ddc:004 open_access

Public Coin Interactive Proofs for Label-Invariant Distribution Properties Herman, Tal Interactive Proof Systems Distribution Testing Public-Coin Protocols Assume we are given sample access to an unknown distribution D over a large domain [N]. An emerging line of work has demonstrated that many basic quantities relating to the distribution, such as its distance from uniform and its Shannon entropy, despite being hard to approximate through the samples only, can be efficiently and verifiably approximated through interaction with an untrusted powerful prover, that knows the entire distribution [Herman and Rothblum, STOC 2022, FOCS 2023]. Concretely, these works provide an efficient proof system for approximation of any label-invariant distribution quantity (i.e. any function over the distribution that’s invariant to a re-labeling of the domain [N]). In our main result, we present the first efficient public coin AM protocol, for any label-invariant property. Our protocol achieves sample complexity and communication complexity of magnitude Õ(N^{2/3}), while the proof can be generated in quasi-linear Õ(N) time. On top of that, we also give a public-coin protocol for efficiently verifying the distance a between a samplable distribution D, and some explicitly given distribution Q. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tal Herman 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.72 urn:nbn:de:0030-drops-210654 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.72 eng https://creativecommons.org/licenses/by/4.0/legalcode