Research map / Learning theory and algorithms / Sample complexity
How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Builds a computationally sound 4-message interactive argument that lets a verifier with only sampling access check that an unknown distribution is close to any polynomial-time-decidable property, using ~sqrt(N)/eps^2 samples and communication via CRH-based succinct distribution commitments and IAPs.
Problem
Verifying, without replicating the analysis, that an unknown distribution (accessible only via samples) is close to having a claimed distribution property, with sublinear samples, communication and verifier time.
Approach
A prover commits to a distribution via a CRH-based hash tree (succinct distribution-commitment with local openings for pdf, cdf, quantile, sampling); the verifier runs an identity tester against the committed distribution using samples from D, and an interactive argument of proximity over the sorted-grain string representation verifies the property decision in polynomial time.
Key results
- Protocol uses 4 messages with verifier sample complexity and communication roughly O~(sqrt(N)/rho^2) poly(kappa), with a quadratic speedup over replicating analysis for properties requiring quasi-linear samples.
- Sample complexity matches the Omega(sqrt(N)/rho^2) lower bound up to polylog(N) factors.
- Honest prover runs in poly(N, kappa) time and uses O~(N) poly(1/rho) samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a prover and the proposed argument system instead of standalone testing | Verification of efficiently decidable distribution properties · Distribution properties over [N] | verifier sample complexity: \widetilde{O}(\sqrt{N}/\rho^2) \cdot {\sf poly}(\kappa) vs. \Omega(N/\log(N)) | Helped |
| Use the proposed protocol rather than replicating the analysis | Properties whose standalone analysis requires quasi-linear sample complexity and running time · Distribution properties over [N] | verification efficiency: quadratic speedup | Helped |
| Use the proposed argument system instead of the Chiesa and Gur protocol | General distribution properties · General distribution properties | communication complexity: \widetilde{O}(\sqrt{N}/\rho^2) vs. quasi-linear | Helped |
| Use the proposed argument system instead of the Chiesa and Gur protocol | General distribution properties · General distribution properties | verification time: \widetilde{O}(\sqrt{N}/\rho^2) vs. quasi-linear | Helped |
Limitations
- Soundness is only computational, relying on collision-resistant hash functions; not unconditional.
- Honest prover relies on PCP machinery with large overheads, and the protocol is presented with a perfect-knowledge prover idealization.
- Huge-domain extension requires bounded support size N in both YES and NO cases.
Experimental setup
Metrics: sample complexity communication complexity verifier runtime
Baselines: Chiesa and Gur non-interactive protocol Herman and Rothblum label-invariant protocols
Builds on: interactive arguments of proximity Chiesa and Gur unconditionally sound distribution protocol Herman and Rothblum label-invariant protocols Kilian 4-message argument
Closest papers by meaning
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.86)
- Efficiently Verifiable Proofs of Data Attribution (NeurIPS 2025 · similarity 0.84)
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.84)
- Replicable Uniformity Testing (NeurIPS 2024 · similarity 0.83)
- Differentially Private Equivalence Testing for Continuous Distributions and Applications (NeurIPS 2024 · similarity 0.82)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.