Arrow Research search

Author name cluster

Tal Herman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
1 author row

Possible papers

5

ICLR Conference 2025 Conference Paper

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions

  • Tal Herman
  • Guy N. Rothblum

As statistical analyses become more central to science, industry and society, there is a growing need to ensure correctness of their results. Approximate correctness can be verified by replicating the entire analysis, but can we verify without replication? We focus on distribution testing problems: verifying that an unknown distribution is close to having a claimed property. Our main contribution is an interactive protocol between a verifier and an untrusted prover, which can be used to verify any distribution property that can be decided in polynomial time given a full and explicit description of the distribution. If the distribution is at statistical distance $\varepsilon$ from having the property, then the verifier rejects with high probability. This soundness property holds against any polynomial-time strategy that a cheating prover might follow, assuming the existence of collision-resistant hash functions (a standard assumption in cryptography). For distributions over a domain of size $N$, the protocol consists of $4$ messages and the communication complexity and verifier runtime are roughly $\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$. The verifier's sample complexity is $\widetilde{O}\left(\sqrt{N} / \varepsilon^2 \right)$, and this is optimal up to $\text{polylog}(N)$ factors (for any protocol, regardless of its communication complexity). Even for simple properties, approximately deciding whether an unknown distribution has the property can require quasi-linear sample complexity and running time. For any such property, our protocol provides a quadratic speedup over replicating the analysis.

Details

FOCS Conference 2025 Conference Paper

Proving Natural Distribution Properties is Harder than Testing Them

  • Tal Herman
  • Guy N. Rothblum

Suppose that an untrusted analyst claims that it ran a distribution tester and determined that an unknown distribution has a certain property. Can the untrusted analyst prove that its assertion is correct to a verifier that does not have sufficient samples and computational resources to run the tester on its own? In this work, we are interested in proofs that can be generated very efficiently, with minimal overhead over running the distribution tester. In particular, since the distribution tester is sublinear (in the domain size), at the very least we also want the sample complexity for generating the proof to be sublinear. Do natural properties that have sublinear testers admit such proof systems? Our main result answers this question negatively for several natural properties. For these properties, if the verifier’s sample complexity is non-trivial (smaller than just running the tester on its own), then the (honest) prover must draw a linear number of samples. We show this result for the problem of testing whether the distribution is uniform over its support, for specifying the distribution’s k-collision probability (or its L k norm), and for other natural properties. Our results shed light on a recent line of work showing that if we allow the prover to draw a quasi-linear number of samples, then many distribution properties have proof-systems with very efficient verification. Our negative results imply that the super-linear sample complexity of the prover in those proof-systems is inherent.

Details

FOCS Conference 2024 Conference Paper

Interactive Proofs for General Distribution Properties

  • Tal Herman
  • Guy N. Rothblum

Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using fewer resources (say in terms of samples and computation) than would be needed to run the analysis herself? We construct an interactive proof system for any distribution property for which the distance from the property can be computed by (log-space) uniform polynomial size circuits of depth D, where the circuit gets a complete description of the distribution. Taking N to be an upper bound on the size of the distribution's support, the verifier's sample complexity, the running time, and the communication complexity are all sublinear in N: they are bounded by O(N 1-a +D) for a constant a > 0. The honest prover runs in poly(N) time and has quasi-linear sample complexity. Moreover, the proof system is tolerant: it can be used to approximate the distribution's distance from the property. We show similar results for any distribution property for which the distance from the property can be approximated by a bounded-space Turing machine (that gets as input a complete description of the distribution). We remark that even for simple properties, deciding the property without a prover requires quasi-linear sample complexity and running time. Prior work [Herman and Rothblum, FOCS 2023] demonstrated sublinear interactive proof systems, but only for the much more restricted class of label-invariant distribution properties.

Details

FOCS Conference 2023 Conference Paper

Doubley-Efficient Interactive Proofs for Distribution Properties

  • Tal Herman
  • Guy N. Rothblum

Suppose we have access to a small number of samples from an unknown distribution, and would like learn facts about the distribution. An untrusted data server claims to have studied the distribution and makes assertions about its properties. Can the untrusted data server prove that its assertions are approximately correct? Can a short efficiently verifiable proof be generated in polynomial time? We study doubly-efficient interactive proof systems that can be used to verify properties of an unknown distribution over a domain $[N]$. On top of efficient verification, our focus is on proofs that the honest prover can generate in polynomial time. More generally, the complexity of generating the proof should be as close as possible to the complexity of simply running a standalone analysis to determine whether the distribution has the property. Our main result is a new 2-message doubly-efficient interactive proof protocol for verifying any label-invariant distribution property (any property that is invariant to relabeling of the elements in the domain of the distribution). The sample complexity, communication complexity and verifier runtime are all $\widetilde{O}(\sqrt{N})$. The proof can be generated in quasi-linear $\widetilde{O}(N)$ time and sample complexities (the runtimes of the verifier and the honest prover hold under a mild assumption about the property’s computational complexity). This improves on prior work, where constructing the proof required super-polynomial time [Herman and Rothblum, STOC 2022]. Our new proof system is directly applicable to proving (and verifying) several natural and widely-studied properties, such as a distribution’s support size, its Shannon entropy, and its distance from the uniform distribution. For these (and many other) properties, the runtime and sample complexities for generating the proof are within polylog $(N)$ factors of the complexities for simply determining whether the property holds.

Details
v2026.09.13