How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
Authors: Tal Herman
Guy N. Rothblum
Venue: ICLR 2025 Poster (2025)
Keywords: property testing
distribution testing
interactive proofs
data science
verification
Primary area: alignment, fairness, safety, privacy, and societal considerations

Abstract: 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.

Published as a conference paper at ICLR 2025
HoW TO VERIFY ANY (REASONABLE) DISTRIBUTION PROPERTY: COMPUTATIONALLY SOUND ARGUMENT SYSTEMS FOR DISTRIBUTIONS
Herman
Guy Rothblum
Weizmann Institute of Science Rehovot, Israel
Apple
{rothblum 0 um. mit edu
(tal. he (eramn @wei zmann ac 1.
ABSTRACT
As statistical analyses become increasingly central, there is growing need to en- sure their results are correct. Approximate correctness be verified by replicat- ing the entire analysis, but can we verify without replication? We focus on distri- bution testing problems: given samples from an unknown distribution, the goal is verifying that the distribution is close to having claimed property. Our main con- tribution is an interactive protocol between verifier and an untrusted prover who both have sampling access to the unknown distribution. Our protocol can be used to verify a very rich class properties:
only requirement that, given a full and explicit description of distribution, it should be possible to approximate its distance from the property in polynomial time. For any such property, if the distri- bution is at statistical distance from having the property, then the verifier rejects with high probability. This soundness property holds against any polynomial-time strategy that cheating prover might follow, assuming the existence of collision- resistant hash functions (a standard assumption in cryptography). For distributions over domain of size N, the protocol consists of 4 messages and the communi-
cation complexity and verifier runtime are roughly δ ( (e2/ The verifier's
sample complexity is Ō (VN/E²). and this is optimal up to polylog(NV) factors (for any protocol, regardless of its communication complexity). Even for simple properties, approximately deciding whether an unknown distribution has the prop- erty can require quasi-linear sample complexity and running time. For any such property, our protocol provides quadratic speedup over replicating the analysis.
INTRODUCTION
Statistical analyses on valuable datasets routinely guide high-stake decisions in domains as diverse as public policy, medicine and finance, and their importance is growing rapidly. As the stakes for data science computations grow, it is increasingly important obtain assurances that the results of the analyses are correct. An emerging line of work takes a novel approach to tackling these questions: using proof-systems from the theoretical computer science literature supply vefifiie proofs for the correctness of data science computations.
We focus on a setting where we have i.i.d. sampling access an unknown distribution, and we want to learn about the properties of the distribution. We can learn by collecting samples from the distribution and performing a sophisticated analysis, but this is expensive, both in terms of sample complexity and the computational complexity of performing the analysis on the collected dataset. Suppose that an untrusted data analysis firm claims to have painstakingly assembled a large collection of samples drawn from the distribution, to have run the analysis, and arrived at some conclusions (for price, of course). Can the firm provide proof that would let us verify their claims about the distribution's properties? If we don't 't have any access to the distribution, then verification impossible, but can we verify using fewer samples and computational resources than we would needed perform the analysis ourselves (i.e. without replicating the analysis)?

---

Published as a conference paper at ICLR 2025
In this work, we focus interactive and probabilistic computationally sound proof systems. The proof is a protocol between the verifier and an untrusted prover, who both have sampling access to the unknown distribution. The prover's claim is that the distribution has (or is close to having) property, as in the distribution testing literature. If the prover's claim is correct and it follows the protocol, then the verifier accepts with high probability. If the claim is far from correct, i.e. the distribution is far from the property. then no polynomial-time cheating prover can make the verifier accept with non-negligible probability. This latter soundness property is proved under (standard) cryptographic assumptions: in particular, assuming the existence of hash functions where it is com- putationally hard to find collisions
hash function families, see Definition AA.9. Our focus on distribution properties draws inspiration from the property testing literature [oldre- ich et al. (1998); Rubinfeld & Sudan (1996) and builds on a study of unconditionally sound proof systems for distribution properties initiated by Chiesa and Gur Chhiesa & Gur (2018) and developed
in recent works of Herman and Rothblum Herman & Rothblum (2022) 2023 2024). Following the cryptographic literature, refer to computationally sound protocols (interactive) argument
systems, whereas unconditionally sound protocols are referred to as (interactive) proofs.
We aim to construct argument systems where the verifier is as efficient possible: the primary resources we consider (and aim to minimize) are the verifier's sample complexity and running time, as well the protocol's communication and round complexities. In particular, the verifier's sample complexity should be significantly lower than the sample complexity needed to decide whether the distribution is (close to being) in the property in the standalone setting (i.e. without a prover). On the (honest) prover's side, we also want the time and sample complexities needed for generating the proof be as small as possible. The proof system should be doubly-efficient Goldwasser et al. (213);; Herman & Rothblum (2023): generating the proof should be possible in polynomial time and sample complexities.
1.1 OUR RESULTS: ARGUMENT SYSTEMS FOR GENERAL DISTRIBUTION PROPERTIES
We show that essentially any reasonable property (see below) has an efficiently verifiable argument system. Taking N to be a bound the size of the domain, the communication and the verifier's sample complexity are (VVN). For many natural properties, the sample complexity needed to decide the problem in the standalone setting (without an untrusted prover) is quasi-linear in N, so our protocol provides a quadratic speedup over replicating the analysis.
We proceed to detail this result: a distribution property is set of distributions (similarly to the way a language a set of strings), parameterized by the size N of the domain. We measure the distance of a distribution D from a property IT by D's total variation distance to the closest distribution in II. We study families of properties characterized by the computational complexity of deciding, given the full specification of distribution, whether it is 8.-close to the property (the YES case), or ffr from the property (the NO case). A Turing Machine for this problem gets as its input the parameters δz, and list ((i, D(i))) LeEN) specifying the probability of each element in the support (probabilities are diseretized to poly(1/N) precision) I computational problem: the distribution is fully specified, there is no need to draw samples. We say that a distribution property can be -a)apppoxii decided (or "approximated") in polynomial time if there exists poly-time Turing machine that decides the aforementioned decision problem for every de, ōy s.t. (6,- 5.) 2 p(N). This is an incredibly rich family of distribution properties: it captures essentially any property that can be reasoned about in poly(N) (see Appendix A. for a formal definition)
We emphasize that this is purely
Theorem 1.1 (Main result: computationally sound arguments for all efficient properties)
Assume the existence of collision-resistane hash family (Definition A. A.9 and let k = s<N) be
'One can consider different natural representations. Many of these are equivalent under polynomial-time reductions. They are thus interchangable for polynomial-tine time Turing machines, and we fix the above represen- tation.
FFor examples, distribution properties that are not efficiently decidable include the property of all distribu- tions supported only on a noncomputable set of integers. Another example is the distribution property defined through a family of graphs parameterized by N, with [N] vertices: consider the distribution property of being supported over N/2-clique of the respective graph for every N. Since this problem is NP-complete, it is efficiently decidable only P-NP.
2

---

Published as a conference paper at ICLR 2025
cryptographic security parameter. For every approximation parameter p p(N) ((1/VN),1) and every property that can be p(N) -approxxxiia decided in poly(N) time, there is a computationally-sonne argument system as follows. The prover and the verifier get input integer N and proximity parameters te,ef ef E [0, s.t. 6s 2 Pb and sampling access to distribution D over [N), where
Completeness: if D is ec-close to the property and the prover follows the protocol, then the verifier accepts with all but negligible probability (smaller than any inverse polynomial).
Soundness: if D is f-ffar from the property, then, for every poly(N, ..)-time non-uniform cheating prover P, the probability that the verifier accepts in its interaction with P is negligible.
Efficient verification: the communication complexity, the verifier's sample complexity and runtime are all ((VN/p2) poly(x). The protocol has 4 messages.
Doubly-efficient prover: the honest prover's 's sample complexity is ((NN)-pol(L//)) and its runtime is poly(N,m)
For simplicity, we assume throughout that the security parameter is small polynomial in N. We emphasize that the protocol achieves tolerant verification Parnas et al. (2006): the verifier should accept even if the distribution is not in the property, so long as close to the property. The complexity is polynomial in the gap p= (c, - <e) between the distances. Tolerant verification can be used approximately verify the distribution's distance to the property: if the prover claims the distance is 6, we can verify this (up distance by setting 6, = 5 and e, 5 + p in proof system, from which Similarly, setting & 8 a and ey 5 yields a lower bound to the distance. In the distribution testing setting (without a prover) tolerant testing is a notoriously hard problem: many well-studied problems require quasi-linear sample complexity (see below). For clarity of exposition, protocols presented as if the honest prover has perfect knowledge of the distribution, but this idealized honest prover can implemented by an honest prover that learns nufficiently-accuee approximation the distribution.
possible to conclude the distance is at most + p with high probability.
On the complexities. Our protocol's sample complexity is nearly optimal: even non-toleram ver- ification of simple properties requires 2 D2vNN/P /p²)) samples (indeed where p is the distance param- eter). This holds regardless of the communication round complexities Chiesa & Gur (2018); Herman & Rothblum (2022) (their proof extends to computationally sound argument systems). As noted above, for distribution testing without a prover, and especially for tolerant testing, many prop- erties require linear or quasi-linear S(N/ log( N)) sample complexity. For example, this is true for tolerant uniformity testing, approximating the support size or the Shannon Entropy and more Raskhodnikova et al. (2009); Valiant & Valiant (2010). Since proving is at least as hard as testing (running the prover and the verifier together gives a tester), any honest prover that seeks to prove these properties will require ((N) sample complexity and runtime. Note that our prover runs in polynomial time and achieves quasi- quasi-linear sample complexity. This sample complexity is thus opti- mal up to polylog(N) factors and dependence on the distance parameter.
Huge domain, bounded support. The result of Thcorem can be extended to distributions over huge domain U, so long as the support size of the distribution is bounded by N (we need this bound to hold in both the YES case and the NO case). The complexities all incur a poly-logarithmic overhead in R2] The extension follows immediately from general Herman and Rothblum (Herman & Rothblum 2024| Section 7). As argued in Herman & Rothblum 2024), this is quite natural setting: for example, it lets verify properties of distribution over at most M individuals, even if each individual's representation can come from a rich domain.
technique of
The setting where p(N) E ((//NN, 1) is the main setting interest for our problem. In addition, for 1 //N our protocol's communication complexity is at least linear, and we might as well use the protocol where the prover sends complete description of the distribution the verifier (see below).
3

---

Published as a conference paper at ICLR 2025
Comparison to unconditionally sound protocols. Chiesa and Gur Chiesa & Gur (2018) pre- sented an unconditionally sound non-interactive protocol for general distribution properties. Their protocol, however, is not sublinear: verification requires quasi- linear communication and verifica- tion time. The sample complexity, however, is only O(v /p²) (similar to protocol). Sub- sequent work, ours included, has focused on sublinear-tine time verification. Herman and Rothblum Herman & Rothblum (2022) 2023) constructed sublinear and unconditionally sound protocols for sample and communication complex- ities (see also Section 1.3) Our new protocol is only computationally sound (and assumes CRHs), but applies to a much richer class of distribution properties. Further, the polynomial dependence on in the communication and the sample complexities is much better (for the sample complexity is tight, see above). A very recent work Herman & Rothblum (2024) constructs unconditionally sound protocols for any property that be approximately decided in bounded-den depth (and polyno- mial size) or bounded-space (and polynomial time). Here too, our class of properties is richer (there no depth or space restriction on the approximate decision procedure). Their protocols also have Ö(N1-a)- poly(1/p) p) sample and communication complexities for constant < 0.1: i.e. the gaps with the complexity in our work are even larger.
the class of label-inaarians properties with
About public-coin protocols for distribution properties. The protocol behind Theorem I.] re- quires the verifier to draw samples from the distribution D, and send them to the prover, thus pre- venting it from being public-coin protocol, in which the verifier only sends random bits to the prover. It remains open whether this protocol can be made public-coin. We note public-coin pro- tocols allow for the application of many powerful tools Fiat-Shamir heuristic, through which public-coin protocol can be made non-interactive, see Fiat & Shamir (1986). For deeper discussion on public-coin protocol for distributions as well as construction of such protocols for family of distribution properties, see BeeHermann (2024).
example of particular interest is the
1.2 EXTENSIONS AND APPLICATIONS
We discuss several applications of the protocol of Theorem 1.] and an extension to NP properties.
Tolerant verification for monotone distributions, juntas and more. The protocol of Theorem 1.1 be used for tolerant verification of several properties that are not label-invariant and where known testers have prohibitive sample complexity:
1. A distribution over {0, 13"h is monotone if flipping the value of a coordinate from zero to can only increase the probability of an element. Distribution testing and learning prob- lems for monotone distributions were studied in Batu et al. 20 Rubinfeld & Servedio (2005); Rubinfeld & Vasilyan (020)). Taking N 2 our protocol allows a verifier to verify a distribution's 's distance from being monotone using Ō Ö(VN ((VN/e") samples and com- munication. This is in contrast to the situation for distribution testing: the best tester known for separating the case where the distribution is monotone from the case where it is e-far from monotone uses D(NV/log(A) =²)) samples Rubinfeld & Vasilyan (2020).
2. A distribution over (0, 1}" R k--junta if there is a set of at most le features that determine the probabilities of all elements (elements that are identical on those features have identical probabilities). Taking N = 2", Aliakbarpour, Blais and Rubinfeld Aliakbarpour et al. (2016) showed a test using Ō(vN k) samples. Our protocol can be used to verify a distribution's 's distance from being a k-junta (i.e. tolerant verification) using ((VN/E²) samples and communication. Our protocol also applies to the setting of a non-uniform underlying distribution (see Aliakbarpour et al. (2016)). To the best of our knowledge, no testers with less than quasi-linear sample complexity are known for these tasks.
3. Canonne et al. Canonne et al. (2018) studied several properties of discrete distributions over [N]. These include log-concavity, convexity, concavity, monotone hazard rate, uni- modality and t-modality. They showed that tolerant testing for all these properties requires quasi-linear sample complexity N. Our protocol can be used for tolerant verification of all these properties (and other properties, such as piecewise piccewise-polynomial polynomial) using Ö(VN/=²) samples and communication. We remark that the fact that for all properties men-
4

---

Published as a conference paper at ICLR 2025
tioned above, given explicit description of a distribution, there is poly(I)) algo- rithm for approximating its distance from the property.
Verifying ERM learning algorithms. Similarly to an application described by Heemman & Roth- blum 2024), our protocol can also be used in the following supervised learning setting. An untrusted data analyst claims that a hypothesis was produced by a polynomial tion algorithm M on a dataset X of N labeled examples. The argument system of Theorem [.]] an approximate risk minimizer, where the verifier only needs to draw O(VN/E" samples from the dataset X. If the size of the dataset is roughly the VC dimension of the benchmark class H (the optimal sample complexity for agnostic learning), then the verification is sublinear in the VC dimension: provably more efficient than learning would be! The main nov- elty here that our protocol extends the Herman & Rothblum (2024) result any polynomial-time ERM algorithm (their result applied to bounded-space or bounded-depth algorithms) and improves the verifier's sample and communication complexities. We rely, however, on cryptographic assump-
empirical risk minimiza-
can be used to verify that
tions.
Propertics in NP. The result of Theorem I.1 applies to an even richer class of distribution prop- erties. Given the full explicit description of a distribution (an input of length (NN),, we need the problem of approximating the distribution's distance the property be in NP (or rather in FNP, if we view this as search problem). The theorem holds as stated for any such property, except that the honest prover needs to have witness to the distance between the property and (a good approx- imation to) the distribution. For example, this can be useful in proving properties of a distribution over encrypted data, if the prover knows the users' secret keys.
1.3 AN EFFICIENT VERIFIED DISTRIBUTION-ORACLE
The construction behind Theorem utilizes lightweight and efficient sub-protocol that is of in- dependent interest, and can be used to obtain direct and efficient protocols for a rich subclass of distribution properties. Informally, the verified distribution-oracee protocol is computationally sound protocol, where the prover commits to a distribution Q over [N] using a succinct commit- ment. The verifier, who has sampling access an unknown distribution D, can repeatedly query several functionalities for the committed distribution Q, and the protocol guarantees that the prover's s answers are all according single fixed distribution Q and that this distribution is s-close the unknown distribution D (otherwise the verifier rejects w.h.p.). The functionalities that the verifier can query include:
1. The probability of any queried element & E [N].
2. The cumulative mass (the cdf) of all elements up to and including (according to the natual ordering of elements in [N].
3. The distribution's ' quantile function, which maps an input μ E (0, 1] the smallest element
x whose cdf is or larger.
4. Obtaining sample drawn by Q.
The sample complexity, communication and verifier runtime in the protocol are Ö( D(vN)/& where each query can be performed using an additional poly(log(N),, xx) communication (and no further samples from D).
The verified distribution-oracle protocol lets us translate a sublinear-time algorithm that has access to the powerful functionalities described above w.r.t. an unknown distribution and decides a property II, into an argument system for verifying II. The point is that the verifier in the argument system only has sampling access the unknown distribution D. The protocol is lightweight and efficient in the sense that it only uses simple distribution testing tools and cryptographic hash trees, whereas the full protocol of Theorem 1.I uses PCP machinery (see below). In partieular, under reasonable assumptions about the complexity of approximately deciding membership in the property, the honest prover in the lightweight protocol runs in Ö(N) poly(k, 1/p) time.
One direct application of the verified distribution-oran protocol is a lightweight argument sys- tem for label-invariant distribution properties (sometimes referred to as symmetric properties):
5

---

Published as a conference paper at ICLR 2025
properties where changing the labels of elements in the support of distribution does not change membership in (or distance from) the property (see Appendix A.II. A distribution'ss 's distance from label-invariant property only depends on the distribution's 's probability histogram: the number of elements with probability p for each p E (0, 1] (up to an appropriate discretization of probabilities). The verifier can the verified distribution-oracle protocol to obtain very good approximation for Q's probability histogram by drawing samples from Q together with their probabilities, It can then estimate Q's distance from the property, and since Q is guaranteed to be close D. this gives a good approximation to D's distance. Herman and Rothblum Herman & Rothblum (2022) 2023) constructed unconditionally sound protocols for label-invariant properties, but their dependence on the distance parameter P was much larger polynomial.
1.4 FURTHER RELATED WORK
We study the verification of distribution properties via computationally sound interactive argument systems. Unconditionally sound interactive proof systems were introduced by Goldwasser, Micali and Rackoff Goldwasser et al. (1985) in the context of proving computational statements about an input that is fully known the prover and the verifier. Computationally sound arguments were in- troduced by Brassard ct al. (1988) in a similar context. In our work, the distribution can be thought of as the input, but is not fully known to the verifier. We aim for verification without examining the distribution in its entirety, using minimal resources (samples, communication, runtime, etc.). Our work builds on a line of work that studies the power of sublinear time verifiers, who have query access to an unknown string, in unconditionally sound proof systems Ergün et al. (2004); Rothblum jet al. 2013); Gur & Rothblum (2018) and in computationally sound arguments Kalai & Rothblum (201)) Our results are most closely related to the works on unconditionally sound protocols for verifying properties of distributions, where the verifier has sampling access to an unknown distribu- tion (rather than query access string) Chiesa & Gur (2018); |eerman & Rothblum (2022) 2023 2024), and on verifying the result of machine learning a algorithms using a small number of labeled examples Goldwasser al. 202II;; Gur et al. (2024). We differ from prior work on verifying prop- erties of distributions in considering the relaxation to computational soundness, Recently Bell et al. (2024), also using cryptographic assumptions and tools, considered setting where both the verifier and prover have full information about some distribution, and the verifier needs to be convinced that a value (hidden inside a commitment) was indeed drawn from the known distribution. This is in contrast to our work, where the verifier doesn't know the distribution but can only sample from it. Our
(rgüün
allow an untrusted prover to commit to the entire description of the unknown distribution (rather than a single unknown sample from known distribution).
TECHNICAL OVERVIEW OF OUR PROTOCOL
Background. Our protocol builds identity testers from the distribution testing literature Batu et al.] (2001). An identity tester is given an explicit description a distribution Q over a domain [N] e.g. table detailing the precise probability of every element in the domain. The tester is also given sample access to an unknown distribution D over the domain [N]. If D = Q then the tester should accept, but if the statistical distance between D and Q is E or larger, then the tester should reject w.h.p. We emphasize that this problem is in the standalone distribution testing model (i.e. there is no untrusted prover). The sample complexity of identity testing is O(vN/E² Valiant & Valiant (0014).
Chiesa and Gur Chiesa & Gur (2018) suggested natural protocol that uses identity testers to verify general distribution properties: the untrusted prover sends a complete description of a distribution Q, and alleges that this describes the unknown distribution D. The verifier, who doesn't 't trust the prover, uses an identity tester to verify that Q is not far from D. If this is the case, then Q can be used as surrogate for D in determining membership in (or distance from) the property. Further, since Q is fully specified, the verifier can decide its membership in (or distance from) any efficiently decidable property: this is purely computational problem and additional samples from D are needed.
The issue is that sending the description of the distribution requires linear communication (to specify the probability of each element), whereas we are interested in protocols with sublinear communica- tion complexity and verification time. Moreover, the verifier needs to run the procedure that decides,

---

Published as a conference paper at ICLR 2025
given Q's description, whether the distribution is in the property. For the general class of properties we study, this latter test can require arbitrary polynomial runtime (even the linear time needed to "read" the distribution description is more than we can afford).
What does the identity tester need to know about Q? Identity testers use samples drawn from the unknown distribution D. together with information about the known distribution Q. A key ques- tion in our work is exactly what the identity tester needs know about Q. Focusing on an identity tester of Goldreich (Goldreich 2017 Section 11.2.2) with optimal O D(NN/e) sample complexity, we show it only needs access to an oracle that, for an element x E [M], provides the probability Q[x]], together with the ability to draw samples from Q.
We focus on the requirement of giving the tester access to an oracle that answers queries x E [N] with Q|0]] (we ignore the issue of sampling from Q for now). We might consider the following naive protocol: the verifier runs the identity tester and asks the untrusted prover to specify the probability Q assigns to elements the tester queries, and accepts iff the identity tester accepts. The problem with this naive approach is that a cheating prover can answer the verifier's queries in way that is not consistent with any global distribution Q. There are two issues: first, the cheating prover can be adaptive, so the probability that it specifies for an element can depend on the other elements queried by the verifier. Second, even if the prover were non non-adaptive and answered each query x using fixed probability determined in advance, there is guarantee that the different probabilities specified for each element specify a probability distribution, i.c. that they sum to 1, and this can lead to the identity tester failing. How can we ensure that the untrusted prover answers the verifier's queries using a fixed and valid underlying distribution without having it send (and commit to) a complete description of the distribution?
2.1 SUCCINCT DISTRIBUTION-COMMTEE
WITH LOCAL OPENINGS
We use cryptographic hashing to design a scheme by which the untrusted prover first commits the entire distribution by sending short digest (much shorter than the description of the entire distribu- tion). For the honest prover, it can send a digest that allows it to verifiably open the probability of any element x E [N]. The opening includes proof of correctness, and it is local in the sense that verifying its validity only requires poly(log( (N), x) communication and computation. For security, the commitment is binding: for any polynomial-size cheating prover, once it sends a digest, it can only successfully open the probabilities of elements according to a fixed underyling distribution Q Importantly, Q is completely determined by the digest and is guaranteed to be a valid probability distribution (the probabilities of all elements sum up to 1).
We construct such distribution-commimennt using collision-resistan hash functions: families of shrinking hash functions where, given a random function in the family, it is hard to find a pair of inputs mapped to the same output (a collision). The verifier chooses the hash function and sends it to the prover. The prover constructs binary hash tree with N leaves, where for E [N] the x-th leaf is labeled with the probability Q[x)). We define the probability of an internal node to be the sum of the probabilities of its children (equivalently, the probability of internal node is the sum of probabilities of leaves in its sub-tree). The label of each internal node in the tree includes its probability and hash of the labels of its children. The digest is the label of the root of the tree (which should have probability I). The local opening for x E [N] includes all the labels of nodes on the path from the root to x and of their siblings. The verifier verifies consistency of the hash values and of the probabilities (for every internal node on the path, its probability is the sum of probabilities of its children).
ensures that the digest binds the prover to at most one label that it can successfully open for each node in the tree. In particular, for each leaf x E [N] there is (at most) only one probability Q[x]] that the prover can open. We also show that the probabilities of leaves that the prover can successfully open are consistent with a global distribution. This latter security guarantee formalized using an extraction-basee definition: given the digest and black-box access to cheating prover, we can extract Q efficiently.
We remark that the prover might refuse to open some locations in the hash tree, or open them in a way that is not consistent with Q and is immediately rejected. The point, however, is that any query that is met with a refusal to open or an inconsistency leads to immediate rejection. Thus, when use the dsirribution-comiiinn
in argument system, the prover's success probability can be
7

---

Published as a conference paper at ICLR 2025
upper-bounded by its probability in mental experiment where all queries are answered using Q Thus, for simplicity and w.l.o.g,, in the techincal overview we assume that the prover answers all queries according to Q See Appendix B for further details and discussion.
We note that distribution-commimmenn draw inspiration from the cryptographic literature on accu- mulators Benaloh & de Mare (1993); [Baric& & Pfitzmann (1997) and a construction of Buldas et al.) (2000). An accumulator is a commitment to set of values, whereas we need the commitment to specify probabilites for the values, and for these probabilities to sum to 1.
Recovering the edf and sampling from Q. Our protocols also need the ability to locally open, for any æ E [M]] the cumulative probability of mass Q assigns to the elements up to (and including) x. We denote this edf by (z(z). The hash tree construction supports this functionality using the same opening: the verifier sums the probability of x with the probability of all left-siblings of internal nodes the path from x to the root. Access to the cdf function is important for our protocol for general polynomial-time properties. It is also useful for supporting sampling from Q (which is used by the identity tester, see above): sample from the verifier picks random probability μ E [0, 1] and asks the prover to open the smallest element z whose edf is at least (the quantile function). See further details in Appendix B
2.2 VERIFIABLE DISTRIBUTION-ORACII
In our protocol, the untrusted prover commits to Q using the dnstributioncoomminne The verifier then runs an identity tester, drawing samples from the unknown distribution D, and using the local opening to obtain all the information it needs about Q for each of its samples. The main point about this protocol is that the communication much smaller than the complete description of Q: the digest is short, and each opening is of (olylog(NV) length. The identity tester uses O(VN/E") samples, so the total communication and verification time are Ö(VN/e?).
The identity tester guarantees that Q is close to the unknown distribution D (otherwise the verifier scheme allows the verifier to recover the proability and
rejects w.h.p.). The distribution-comminne the edf of any element [N]. answer quantile queries, and to sample form Q (see above). Thus, can be used towards direct and efficient protocols for a rich sub-class of distribution properties, including iibel-invariant properties. See Section L.3
2.3 VERIFYING PROPERTIES IN P (AND BEYOND)
Our main result is an interactive argument system for verifying any efficientl-decidabbe distribution property. We assume there is a (oly(Me Turing machine M that, given as input a complete description of a distribution Q over [N] (say as a list of elements and their probabilities), computes Q's distance the property II, up to a additive approximation error.
Interactive arguments of proximity (IAP). Our construction uses IAPs Rothblum et al. 2013);; Kalai & Rothblum 2015); protocols for deciding approximate membership of an input string X 10. in a language L. The verifier has query access to the input. It should accept the input is in the language. If the input e-far from the language in relative Hamming distance, then no polynomial-size cheating prover should be able to get the verifier to accept (except with negligible probability). Assuming the existence of relistatn-resistant hash functions, any language in P has an IAP that proceeds in two steps: first, in the communication phase, the verifier and the prover commu- nicate in 4-message protocol with communication complexity and verifier time poly(Log(N)) k)/s. The verifier does not access the input in the communication phase. In a subsequent query phase, the verifier makes (1/E) queries to the input and accepts or rejects. The protocol uses the PCP the- orem, which induces overheads for the prover. It may be possible to reduce this overhead using recent advances from the proof-system literature RReingold al. (2016); Ben-Sasson et al. (2016); Ron-Zewi & Rothblum 2022). See Section A.3 for further details.
Our protocol. At high level, the protocol operates as follows:
The prover commits to the distribution D via digest d, using the scheme of Section 2.1
8

---

Published as a conference paper at ICLR 2025
The prover and the verifier run the verified distribution-commiine protocol of Section
2.2 to verify that the digest d commits the prover distribution Q that is E-close D.
This requires Ó(VN)/E² samples from (this is the only step where the verifier accesses D).
The prover and the verifier use a scheme for representing distributions as bit strings and on polynomial-time Turing machine M'' follows. For any distribution D' over [N], let its representation be X (a bit string). If D' is in II then .M' accepts Xpr. If D' is E-far from the property (in total-variation distance), then X is ((s) far in (relative) Hamming distance from any string that M' accepts. The prover (who knows D) can compute its representation Xp but the verifier cannot. However, the distrbbution-comiineee scheme allows the verifer to query the representation Xi of the distribution Q that the prover committed to using the digest d (more on this below).
The prover and the verifier run interactive argument of proximity (IAP) to check if M accepts Xa. We emphasize that the IAP is for languages defined over strings. This is where the verifier needs query access to X
Completeness follows directly: focus the soundness argument. Since Q and D are close, Q must be far from the property. Thus, the representation guarantees that Xa is far from making M accept. The binding property of the commitment scheme and the soundness of the IAP guarantee that the verifier will reject w.h.p.
String representation and consistency. For simplicity, suppose that is 7-grained for E (0, 1/N) Goldreich et al. (2023). Le., that the probabilities of all elements in D) are integer multi- ples of 1j. We represent the distribution D as a string Xn E ()/n) where the alphabet Σ is of size (oly(N). We first divide the mass the distribution into (1/n) "grains", each representing n of the mass of the distribution. Each element with probability D[x]] contributes (D[x//n grains that have value x. We then sort the grains and write them into the string XD. This means that
( D[x)
Vz [n], Vi
XD(i== =I
7
In turn, any sorted string corresponds to distribution in the natural way. Given the string X we can reconstruct the standard representation of D as a list of probabilities using a simple one- pass procedure. The machine M' uses this procedure to decide, given XD. whether D is in the property. By construction, if X is close Xn in Hamming distance (and is sorted), then the distribution D that represents close D (the converse might not hold). The full construction uses high-distance error-corectinn encoding of each element x to get tight relationship between the Hamming distance over strings and the statistical distance over the distributions they represent.
Given a digest specifying a distribution Q, and an index E [(1/n)], the verifier can query the i-th symbol of X & by asking the prover to open the digest d to reveal the smallest element whose edf by Q is at least (17 i) (answering the quantile function, Section 1.3
ACKNOWLEDGMENTS
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement No. 819702) and from the Simons Foundation Collaboration on the Theory of Algorithmic Fairness.
REFERENCES
Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld. Learning and testing junta distribu- tions. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir (eds.), Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, vol- ume 49 of JMLR Workshop and Conference Proceedings, pp. 19 JMLR.org, 2016. URL 6.
'W.Lo.g. we focus non-tolerant verification in this overview. The tolerant case is nearly identical think of new property that checks if D) is the claimed distance from TT.

---

Published as a conference paper at ICLR 2025
Niko Baric and Birgit Pfitzmann. Collision-free accumulators and ftil-stop signature schemes with- out trees. In Walter Fumy (ed.), Advances in Cryptology EUROCRYPT '97. International Con- ference the Theory and Application of Cryptographic Techniques, Konstanz. Germany, May 11-15, 1997, Proceeding, volume 1233 of Lecture Notes in Computer Science, pp. 480-494. URL https://dci wtt./oo.g/0000000
Springer, 1997. doi: 3- 69053 33
Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. Testing random variables for independence and identity. In 42nd Annual Symposium Foun- dations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pp. 442-451. IEEE Computer Society, 2001. doi: 10. 10.1109/SFCS..001.99920
URL https:
7/doi arooi.org/100 10. 1109/ 2001 959920
Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone and unimodal distributions. In László Babai (cd.), Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pp. 381 389-390. ACM, 2004, doi: 10.
14.145/110035521007441 www.ttttte / /tw.//o...... 1tt1///011.1151113333322222 1007414
Zoö Ruha Bell, Shafi Goldwasser, Michael P. Kim, and Jean-Luc Watson. Certifying private probabilistic mechanisms. In Leonid Reyzin and Douglas Stebila (eds.), Advances in Cryp- tology CRYPTO 2024 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22. 2024, Proceedings, Part VI, volume 14925 of Lecture Notes in Com- doi:
puter Science, pp. 348 386. Springer, 2024.
3-03--6839---- 11. URL https: htt.//o..rg///// /10 1007/ 00000007772200 -0--9-88833333 68391-6_11
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. Ro- bust peps of proximity, shorter peps, and applications coding. SIAM J. Comput., 36(4); 889-9744 2006. doi: 10.1137/5009753777444666
URL hattps://aci.oot /o.oorgg..........
950977537054468111
Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Martin
Hirt and Adam D. Smith (eds.), Theory of Cryptography 14th International Conference, TCC
2016-B, Beijing, China, October 31 November 3, 2016, Proceedings, Part II, volume 9986 of Lecture Notes in Computer Science, pp. 31-60, 2016. doi: 10. 10.1007998833-62-556444
URL
https: //oo:///oi... wro.or////oo 1007 978 662 53644-5534
Josh Cohen Benaloh and Michael de Mare. One-way accumulators: A decentralized alternative to digital sinatures (extended abstract). In Tor Helleseth (ed.), Advances Cryptology EURO- CRYPT '93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 of Lecture Notes in Computer Science, pp. 274-285. Springer, 1993. doi: 10. 10.100773-550-44885-77 .24. URL https:t////oooo htttps://doiiorgg/// 1007/3- 540 48285-
24
Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sei., 37(2):156 189, 1988. doi: 10. //doi. Pogi.orr//i 0. 101 6/ 00000200222222222 0000 (88) 90005-0
URL https:
Ahto Buldas, Peeter Laud, and Helger Lipmaa. Accountable certificate management using unde- niable attestations. In Dimitris Gritzalis, Sushil Jajodia, and Pierangela Samarati (eds.), CCS 2000, Proceedings of the 7th ACM Conference on Computer and Communications Security, Athens, Greece, November 144, 2000, pp. 9-17. ACM, 2000. doi: 10. 10.1145/3526003556644 URL https://doi. http://do..org///// 1145 000455//56000 352604
Clément L. Canonne. A survey on distribution testing: Your data big. but blue? Electron. Colloquium Comput. Complex., 22:63, 2015. URL httt::///ccc../////////////////t hpi www.wwebbee... deeb.de/repprt/ 2015/063
Clément L. Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld. Testing shape restrictions of discrete distributions. Theory Comput. Syst. 62(1): 62, 2018. doi: 10.1007/ $00224-00179985-6 /ttt://:/ooo.coo///01000//222222
10

---

Published as a conference paper at ICLR 2025
Alessandro Chiesa and Tom Gur. Proofs of proximity for distribution testing. In Anna R. Karlin (ed.), 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA. USA, volume 94 of LIPIcs, pp. 53:1-53:14. Schloss Dagstuhl Leibniz- URL WtRt:t/t::///d /
Zentrum für Informatik, 2018. doi: 1042300.IP 10. 4230/LITP Tcs. ITCS. 2018.50
Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld. Fast approximate probabilistically checkable proofs. Inf. Comput., 189())135-155, 2004. doi: 10.1016/).c.22003.0.. 00w.0000..9000.50
URL https:
1016/ ic. 2003. 09.
Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to identification and signature problems. In Andrew M. Odlyzko (ed.), Advances in Cryptology CRYPTO '86, Santa Barbara, California, USA. 1986, Proceedings, volume 263 of Lecture Notes in Computer Science, pp- 186-194. Springer, 1986. doi:
URL http:::/ddo..og/////
1007/3-540-4777
Oded Goldreich, Introduction to Property Testing. Cambridge University Press, 2017. ISBN 978- 1-107-19405-2. doi: 10.1017/978 URL http:/ /www www.ww.mb.ddg.ccooomm org/us
Oded Goldreich. The uniform distribution is complete with respect to testing identity to a fixed distribution. In Oded Goldreich (ed.), Computational Complexity and Property Testing- On the Interplay Between Randomness and Compulation, volume 12050 of Lecture Notes in Computer Science, pp. 152-172. Springer, 2020. doi: 10.
URL https:
//doi. 10. 1007/00077770 3-000003-0-0-000000000000 43662-3622 10
Oded Goldreich and Dana Ron. On testing expansion in bounded-degree graphs. Electron. Colloquium Comput, Complex. (20), 2000. URL https: //eccc.//cc...o we zmann. ac. i1/ @ccc 2ecc--reortt///00//000--- 020indxxxx html
Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4))653-750, 1998. doi: 00.1555205003.2850000. URL https:
Oded Goldreich, Guy N. Rothblum, and Tal Skverer. On interactive proofs of proximity with proof- oblivious queries. In Yael Tauman Kalai (ed.), 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachuselts, USA, volume 251 of LIPIcs, pp. 59:1-59:16 16. Schloss Dagstuhl Leibniz-Zentruu für Informatik. 2023. doi: 10. WWW.LIPPCSS.TTCS.002..... URL https: :tte:://cca/ http://o..oo./ org 10. 4230/433112I.. ITCS. 2023.
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In Robert Sedgewick (ed.), Proceedings of the 17th Annual ACM Symposium Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pp. 291-304. ACM, 1985. doi: 10. 10.1145/22145.221778 22145.22178)
URL https::/dci. .ra..org/100 1145/
Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. Delegating computation: Interactive proofs for muggles. J. ACM, 62(4):2: 2015. doi: 10. 10.1145/2699436. URL https: //doi.org/10. 11e./219199944
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive proofs for verifying machine learning. In James R. Lee (ed.), 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Jamuary 6-8, 2021, Virtual Conference, volume 185 of LiPles, pp. 41:1-41::9, Schloss Dagstuhl Leibniz-Zenntrum für Informatik, 2021. doi: 10.4230/LIPics. ITCS.2021.41 URL /
ITCS. 0TTC.20211.1
Tom Gur and Ron D. Rothblum. Non-interactive proofs of proximity. Comput. Complex. 27 (1):99-203) 2018. doi: 10.1007/400037-1166-3336699 URL :tt::://ooooooo 600037-016-0136--

---

Published as a conference paper at ICLR 2025
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, and Igor Shinkar. On the power of interactive proofs for learning. In STOC '24 56th Anmual ACM SIGACT Symposium Theory of Computing (to appear), Vancouver, Canada, June 24-28, 2024. ACM, 2024. S.RI.ttt..ss. / http://.....rr11....8...
2404. 08158 158
Tal Herman. Public coin interactive proofs for label-invariant distribution properties. In Amit Kumar and Noga Ron-Zewi (eds.), Approximation, Randomization, and Combinatorial Opti- mization. Algorithms and Techniques, APPROX/RNDOM 2024, August 28-30, 2024, London School of Economics, London, UK, volume 317 of L.Plcs, pp. 72: 1-72:23. Schloss Dagstuhl Leibniz--Zentrum für Informatik, 2024. doi: 00.4230/LIPICSS APPROIISAPPPO/AAADDDDDAO 2024.72. URL htttt::/p//oootto org/10 4230/ APPROX CEEEPROX/RANDOM...MMMMM RANDOM. 2024.72
Tal Herman and Guy N. Rothblum. Verifying the unseen: interactive proofs for label-invariant distribution properties. In Stefano Leonardi and Anupam Gupta (eds.). STOC '22: 54th Anmual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pp. 1208- 1219. ACM, 2022. doi: 10.1 14513419935.35199999 3519935. 3519987
URL. https: /o wtg.//.000000 1041145/
Tal Herman and Guy N. Rothblum. Doubley-efficiens interactive proofs for distribution properties. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pp. 743-751. IEBE, 2023. doi: 10.1 10.1109/FF0C55599922233000
URL.ttpps: http:/oo..rrrro 11..1...1....... 0ttp://00000011110////5555555590 2 2023 00049
Tal Herman and Guy N. Rothblum. Interactive proofs for general distribution properties. Electron. Colloquium Comput. Complex., pp. 094, 2024. URL
we www.wwwwwwmaa.a..mmmmmmm 11/
Yacl Tauman Kalai and Ron D. Rothblum. Arguments of proximity - [extended abstract]. In Rosario Gemnaro and Matthew Robshaw (eds.), Advances in Cryptology CRYPTO 2015 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part 11, volume 9216 of Lecture Notes in Computer Science, pp. 422-442. Springer, 2015. doi: 10. 978-3-662-48000--| URL Scieenc, wtt.o///////.11/90990//// 662 -600177777777--------000000-0000 662-0800--22
Silvio Micali. CS proofs (extended abstracts). In 35th Annual Symposium Foundations of Com- puter Science, Santa Fe, New Mexico, USA, 20-22 November 1994, pp. 136-453. IEEE Com- puter Society, 1994, doi: 10.1109/SFCS. 1994. URL htttt:tt///ccco wwt.oogg11111
Liam Paninski. A baise test for uniformity given very sparsely sampled discrete data. IEEE Trans. Inf. Theory, 54(10):450-4755, 2008. doi: 10.1109/11T.2008.99 9898888877. URL
/ettss://dot www.loorg/.... http://...11111T..11 2008. 928987
Michal Parnas, Dana Ron, and Ronit Rubinfeld. Tolerant property testing and distance approxi- mation. J. Comput. Syst. Sci.. 1012 2006. doi: 10. j0s06/.ees. URL
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam D. Smith. Strong lower bounds for upproximating distribution support size and the distinct elements problem. SIAM J. Com- doi: 10.1137/070701649, URL htllh:tt/://ae org /0..//10.117/
put., 39(3))813-884) 842, 2009.
07070164 649
Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Constant-round interactive proofs for delegating computation. In Daniel Wichs and Yishay Mansour (eds.), Proceedings of the 48th Anmual ACM SIGACT Symposium Theory of Computing, STOC 2016, Cambridge, MA, USA, doi:
June 18-21, 2016, pp. 49 62. ACM, 2016.
111.4/22887511888877337 URL https:
7/doi. wrw./rr//100
45/2897518 2897652
Noga Ron-Zewi and Ron D. Rothblum. Proving as fast computing: succinct arguments with constant prover overhead. In Stefano Leonardi and Anupam Gupta (eds.), STOC '22: 54th Annual ACM SIGACT Symposhum
Theory of Computing, Rome, Italy. June 20 24, 2022, pp. 1353- 1363. ACM, 2022. doi: 11.1145555199553519955 URL hctps: /ttp////....// http:///t...r/.....//
351 9935. 3519956
12

---

Published as a conference paper at ICLR 2025
Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson. Interactive proofs of proximity: delegating computation in sublinear time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (eds.), Symposium Theory of Computing Conference. STOC' 13, Palo Alto, CA, USA, June 1-4, 2013, 802. ACM, 2013. doi: 10. 241145/2488608824888700 URL https: /oi. org/10.
pp. 702-802. 1145/2488618 2488709
Ronitt Rubinfeld and Rocco A. Servedio. Testing monotone high-dimensional distributions. In Harold N. Gabow and Ronald Fagin (eds.), Proceedings of the 37th Annual ACM Symposium on
Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp- 147-156. ACM, 2005, doi: 10. 10.1145/100090.1000 1060613. CtLnttts::// 1 011.4////00009001000000000 1060613
Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Compud., 25(2):252-271, 1996. doi: 10. 10.1137/50077337932255111
URL httph:ttsssdet /oi /tte:/0....11//00977333333333331
Ronitt Rubinfeld and Arsen Vasilyan. Monotone probability distributions over the boolean cube can be learned with sublinear samples. In Thomas Vidick (ed.). 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, vol- Zentrrum für Informatik, 2020.
ume 151 of LIPles, pp. 28:1-28:34. Schloss Dagstuhl URL httph::t////// / wtt.iiooo/1..3////P/E..... ITCS.
doi: 202 0020.22 28
Gregory Valiant and Paul Valiant. CLT and tight lower bounds for estimating entropy. Electron. Colloquium Compul. Complex., 17:183, 2010. URLpttt:://ccc. http//cccc...p..... web. deeebbbe//eport/
2010/183
Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 51-60, IEEE Computer Society, 2014. doi: N0.1109/FOCS.2014.1 URLhttps: https: http::::///cioooooe org http:///w...rr1111111/0//////00/ 2014
A NOTATIONS AND FORMAL DEFINITIONS
For an integer n N. we use [ni to denote the set (l....,,... We use the natural ordering over integers to order the elements in any subset of [n].
Turing machines. A probabilitic polynomial-time Turing Machine (PPTM) is a Turing Machine that has access to tape cointaining uniformly random i.i.d. coins and runs in polynomial time. A PPTM that participates an interactive protocol augmented with an interaction tape for sending and receiving messages. A non-uniform machine also gets access to polynomial-length advice string (the advice string is fixed for each input length n). We sometimes refer to the running time of non-uniform machine as its size (drawing on equivalences between non-uniform Boolean circuits and non-unine uniform Turing Machines).
An oracle machine with oracle access to probabilistic functionality I' has additional oracle tape where it can write a query & and get back a sample from r(2) at unit cost. The functionality might take empty inputs, in which the machine has sampling access a fixed distribution I.
Distributions. We work with distributions over discrete domains throughout this work. For a set S. we denote the uniform distribution over S by Us. For distribution over a domain of size N. we assume w.l.o.g. that all probabilities are taken up to precision poly(1/N), so an element's probability can represented using (log(N) bits. For a distribution Q over [N], we use Q[x²] E [0, to
denote the probability of E [N]. Similarly, we use (2(x) to denote the cumulative mass of all elements up to (and including) x, i.c P2(x)) = En So ((x].
Definition A.1 The total variation distance (alt. statistical distance) between distributions P and Q over a finite domain X is defined as:
1 Σ
(Pv(P
-Px))-((a)
#EX
13

---

Published as a conference paper at ICLR 2025
A.1 DISTRIBUTION PROPERTIES AND TESTING
Definition A.2 (Distribution properties) A distribution property II (II) NeN is an ensemble of sets of distributions, where IlN contains distributions over the domain [N].
The distance of distribution D over domain from distribution property 11 is
6rv(D, IT) _ inf ())v(D,Q) [Tn]
Definition A.3 (Property tester) An algorithm T that is given parameter N N, distance param-
eter (0, 1), and samples drawn from distribution D over domain [N] is called tester for distribution property II if the following hold:
Df E I1, T accepts with probability at least 2/3.
(f,1)(D,11)) > T rejects with probability at least 2/3.
The success probabilities can be amplified by repetition. The sample complexity is the number of samples T draws from D (as function of N and c).
Theorem AA (Uniformity tester, Goldreich & Ron (2000); Paninski (2008) The sample com- plexity for testing the property of being uniform over the entire domain, i.e. = ((UIN))).
VN
Definition A.S (Label invariant distribution properties) We call distribution property II label- invariant for every D over [N] and for every permulation [N] - [N] holds that:
Dell + x(D)
The family of label-invariant distribution properties contains many well-studied and natural proper- ties, for example: the property U/ of being uniform over the domain (see Theorem A.4), the property of having entropy K (N),, the property of having support size most S(N), the property of being at distance at most 8(N) from uniform distribution over a subset of the domain, etc.
Efficiently decidable properties. We define two families distribution properties where ques- tions like membership in distance from the property be decided efficiently given appropri- ate description the distribution. First, we define label-invariant properties where membership can be decided in polylogarithmic time given the approximate histogram.
Definition A.6 (polylog-time approximately decidable label-invariant properties) A invariant property TI is polylog-time hold.
label-
h T-approximately decidable if the following two conditions
There exists an algorithu Adecides that is given parameters T (0, N E N, and T 7-approximate probability histogram (pş); and runs in poly(lo((N).)) time. If there exists distribution Q over domain [N] with T-approximate histogram (Pi)ş such that 8rv(Q, IIx) S t, the algorithm accepts; and if every distribution consistent with the given histogram satisfies 6yv(Q, IIN) 2T, it rejects.
There exists algorithm Aind that is given parameters N E M and ó. p (0, 1), well as an explicit description of a distribution D over domain [N] such that Srv(D, IIn) S 6. Afind runs in time ((N) (N))poy(55=1 1 p-11), and outputs an explicit distribution Q over domain [N] such that: Q 11 and 8Tv(D, Q) < S
Remark A.7 We view the condition that a property admits the two algorithms described in Defini- tion A.6 as mild. The decide algorithm requires that membership of distribution in property can be approximated efficiently just given its histogram. Herman and Rothblum Herman & Roth- blum 2022 Section 6.2) present decide algorithms for fundamental label-ine invel-inrriant properties: e.g. for approximating the Shannon entropy and the distance from uniform. The find algorithm is also implementable for those properties and many more.
14

---

Published as a conference paper at ICLR 2025
Definition A.8 [Efficient approximately decidable properties] For p(N) (0, 1), distribution II poly-time (or efficiently) p(N) appproxmmate decidable if it admits a poly(N, 1/p) p/tme algo- rithm Dist that receives as input N and an explicit description of a distribution D over domain [Naadd outputs 8 such that:
(,T((D,TT) -ōl P
A.2 CRYPTOGRAPHIC DEFINITIONS
A function f: N + is polynomial-time if there is a poly(x)-time Turing Machine that on input 1 outputs (n)). A function q : N [0, is negligible if for any polynomial p(n), for all but finitely many input lengths, f(n) < 1/p(n). We denote this by q(n) negl(n).
In the cryptographic definitions in this work we focus on non-uniform polynomial time adversaries. In our setting, it is often the case that there is an unknown underlying distribution D over a domain [N], and the adversary has sampling access to D. We remark that any such adversary can be con- verted into non non-unifomn uniform adversary with no access to D by a standard argument (plugging a "good" collection samples into the adversary's non-uniform advice string). This transformation applies even when the domain of the distribution is exponential in the adversary's running time, but in this work we mostly focus on adversaries whose runtime is polynomial the domain size.
Collision- Ressstant Hash Families (CRHs). CRHs are families of length-shrinking functions where, given the description random function the family, it is hard for a PPTM adver- sary to find collision, i.e. +f x' in hi's domain s.t. h(x) = h(x').
Definition A.9 (CRH) Let Lin, lout : N poly(x)-time computable sequences of input and ourput lengths, where YK N, Eou (1)) < Eia (x). A family of collision resistant hash functions (CRHs) is defined by PPTM algorithms Gen and Eval:
* Gen(1*) outputs key, where hkey 10, + 20,11 1)((0) is a function in the family Hşe-
* EEval(key, E (0,1)*) outputs Meyy(a)
For any polynomial-size Adv, the probability that it finds collision is negligible:
Pr key Gen((1)
[(x, t Adu(1", ,key), + x', huee (x) hkee (x') negl(k).
Recall that we allow Adu to be non-uniform. Namely, we assume that the CRHs are secure against non-uniform adversaries. Note also that the existence of CRHs where fout < Lin is equivalent the existence of CRHs with arbitrary polynomial shrinkage. Finally, we note that throughout this work typically assume that the security parameter is (at least) small polynomial in the domain size N of the unknown distribution.
A.3 INTERACTIVE ARGUMENTS OF PROXIMITY (IAPs)
IAPs were informally descrihed in Rothblum al. (2013) and formally studied by Kalai and Roth- blum Kalai & Rothblum (2015). They are camputtaiionall-souute
variants Interactive Proofs of Proximity (IPPs), which were defined and studied Ergün et al.] (2004); Roohbluu al.) (2013). These are interactive protocols for proving membership of an input string in a language. The verifier has query access the input, and should run in sublinear time in the input length. In IAP, no polynomial-tne cheating prover should be able to get the verifier to accept any input that is far from the language (except with negligible probability). The main difference from arguments for distribu- tion properties (our focus in this work, see Section A.4). is that the input to the proof-system is string, rather than distribution, and the verifier has query access to this string, rather than sampling access in the distribution case.
For our definition, we consider an IAP that proceeds in two phases: a communication phase, where the prover and the verifier exchange messages, but the verifier does not query the input, and subsequent query phase, where the verifier queries the input. The verifier then applies a decision predicate its views in the communication phase and the query phase (including any random coins it tossed), and rejects or accepts. See Goldreich et al. (2023) for a more thorough structural study of tublinea-ttime verifiers in proofs of proximity for strings.
15

---

Published as a conference paper at ICLR 2025
Definition A.10 (Interactive Argument of Proximity (IAP) Rothblum et al. (2013); Kalai & Rothblum 2015
An IAP for language is an interactive protocol with two parties: a prover P and a verifier V. Both parties get input length n, proximity parameter E (0, and a secruity parameter 1". The verifier also gets oracle access to an input x E {0, 1]", whereas the prover has full access to T.
The protocol is divided into two phases. In the interaction phase the two parties interact, but the verifier does not access the implicit input. The interaction produces a communication transcript T. In the subsequent query phase, the verifier makes its queries Q into the implicit imput (based on the explicit imput, the transcripl and its random coins r). The verifier then applies a decision predicate by to its views from both phases and accepts or rejects.
1. Completeness: For every input x and > it holds that
(ov(1,,, = =1] =1.
Pr (r,T, (Pla), (lele,,1)
2. Soundness: For every > 0 and x that is e-far from the language C, and for every poly(K, (ml)-time non-uniform cheating prover P it holds that
Pr (r,,,))+ (p- (z), vo ((w),e,1n))
T0((,,,==100) =1 negl(n).
We typically measure the complexity of IAP in terms of the verifier's query complexity, the communication complexity, the number of rounds, and the prover's and the verfier's runtimes (the verifier's runtime taken over both phases). We note that the division of the protocol into commu- nication and query phases is (to a large extent) without loss of generality: even if the verifier needs to know values of the input on-the-fly during the communication phase, can ask the prover for the values the input takes those queries, and then check the prover's answers in the query phase. As we do throughout this work, we typically assume that the security parameter is at least a small polynomial in the input length
Theorem A.11 (IAPs for NP Rothblum et al. (2013) Let L be NP language, E= E(n) a prox- imity parameter and K k(n) a security parameter. Assuming the existence of collision-resisteee hash functions (see Definition A.9. has public-coin 4-message IAP for e-proximity with query complexity (11/E). The communication complexity and verifier runtime are (poly(log(m) k)/E).
The honest prover, given witness the input x e's membership C, runs in poly(n, k) time.
The protocol also applies to languages P. where the witness for membership empty: the honest prover runs in polynomial time given only the input, with additional auxiliary information. The construction builds on Kilian's 's 4-message argument system for NP languages. The idea is for the prover to commit to locally testable and locally decodable encoding of the input, as well as PCP of proximity [Ben-Sasson et al. (2006) for the input's membership in the language. The commitment should be succinct and locally-openable string commitment, which can be based on any CRH family (e.g. using hash tree). The verifier in the argument system gets the commitment. runs the PCPP verifier, and asks the prover open its queries into the proof and the input encoding. also checks that the committed input encoding is (close to) valid encoding of a string x'' that is e-close the input z. This can be done by locally testing the committed encoding and locally decoding ((1/e) random locations in the message inside the encoding (the local testing and decoding use the local opening the commitment scheme). The values of the decoded locations the committed message compared to the actual input. This latter check is the only place where the argument's verifier accesses the input, and is performed during the query phase.
Finally, we note that Rothblum et al. (013)) suggested that the protocol could be made non- interactive using the Fiat-Shamir heuristic Fiat & Shamir (1986), as proposed by Micali Micali (1994). Soundness would be heuristic, could be proved in the random oracle model. Kalai and Rothblum Kalai Rothblum (2013) showed a 2-message protocol for languages in P. based on a stronger cryptographic assumption.
16

---

Published as a conference paper at ICLR 2025
A.4 INTERACTIVE ARGUMENTS FOR DISTRIBUTION PROPERTIES
We consider interactive protocols consisting of a prover and a verifier (P, V), where the parties send messages back and forth (in our protocol the first message is sent by the verifier). In an argument system for a distribution property, the prover and the verifier both get black-box sampling access to an unknown distribution D. The protocol's prover and verifier sample complexities are the total number of samples drawn by each of the parties. The protocol's communication complexity (the total number of bits sent), round complexity (the total number of messages sent by both parties), and the total runtimes of both parties are defined in the natural way.
Definition A.12 (Interactive argument system for tolerant distribution testing) A tolerant in- teractive argument system for a distribution property II is an interactive protocol (P, V) where the prover and the verifier both get as explicit input the domain size N. the (unary encoding of the) security parameter 1", and proximity parameters te S 65. The prover and the verifier also both get black-box (oracle) sampling access to a known distribution D. For every N, E and ce S Cf (0,1). for every distribution D over the domain [N]:
* -Completeness: if 8rv(D, eo the verifier V, interacting with the prover P, accepts with all but negl(n) probability.
Soundness: if ÓTv(D, 2 ej, then for every polynomial-Se size non-uniform cheating prover strategy P, the verifier V, interacting with P, rejects with all but neg)(s) probabil- ity.
We typically measure the runtime of the verifier and the (honest) prover as a function of N, K. P = (cf - (e). We aim for the honest prover to be (at most) polynomial in these parameters. The verifier rypically required to be sublinear in N. Throughout this work we allow the cheating prover to run in poly K. K., p) non-uniform time
For simplicity, we assume throughout this manuscript that N and x are polynomially related.
B SUCCINCT DISTRIBUTION-COMMIINN
A Distribution-comminne allows sender to commit to a distribution Q over a domain [N] using succinet digest d. The digest can later be used by receiver (or verifier) to "locally" open the probability that Q assigns to any element x E [M] in a verifiable way (see below). Moreover, the commitment scheme up to (and including) x using the natural lexicographic ordering over elements in [N]. We refer to these probabilities as the pdf and the edf of x (respectively). For security, we require that PPTM adversary can produce a digest that allows it to locally open the probabilities of an element in two different ways. Moreover, successful openings are always consistent with a (unique) distribution that is specified by the digest. Of course, an adversary might send a digest and then later refuse to open the probability of particular element (or a set of elements), but we require that once a digest has been sent, there is a unique and well-defined distribution Q s.t. the adversary can only get the receiver to accept probabilities according to Q We emphasize that this is the case even though the digest short (its size depends only on the security parameter, independent of N), whereas explicitly describing the distribution could require communicating Ö(N) bits.
construct also supports opening the cumulative mass (2) of elements
Efficient extraction. An adversarially produced digest induces a distribution Q. We require that, once the digest is specified, the distribution Q can "extracted" in polynomial time by an extrac- tion algorithm. The extractor gets black-box access to an adversary who produces a sequence of elements and opens their probabilities. Given any such PPTM adversary, the extractor produces full description of a well-specified distribution Q. and the adversary cannot successfully open the probabilities (the pdf and the cdf) of any element x except to Q[x] and E (3(x)) (x) (respectively).
'oore generally, it is also interesting to consider huge domains, i.c. much larger than poly(k). In this case, one can consider poly(w) (x)- adversaries, whose running time is sublinear in the domain size.
17

---

Published as a conference paper at ICLR 2025
Definition B.1 Diistibutton-Commitnerr A distrbuttion-commiinent scheme has PPTMs Gen, Dig, Open, Voommit and Ext as follows.
Gen(1", .N) outputs key.
Dig(key, Q) gets as input a key generated by Gen and description of a distribution Q over [ It oulputs a short digest of length poly(k) and auxiliary information aux to be used in generating proofs (aux can be of length (k)
Open(x, key, d, aux), on input Dig, outputs [[z), Φ2 (x) E [) and a proof v of length poly(R, (n, log(N))-
[N), digest and auxiliary information produced by
Veommit (z. p. key, d, T),, gets as input element x E [N] and its alleged paf and cdf p.q E [0, 1] and a proof n. Accepts or rejects the proof and runs in poly log(N)) time.
Ext (key, 1% d, 1P) gets black-box access to an adversary algorithm. Adv with alleged (polynomial) success probability p (0,1) and outputs description Q of a distribution over [N].
An honest sender who commits to distribution Q using Dig can open the probabilities p Q[x],1 = (2) of any element a E [N), producing proof that will (always) be accepted by Voommit.
For security, we consider a PPTM adversary Adv = (Adv1, Advg) that operates in two steps (the first step outputs a state that used by the adversary in the second step). In the first step, Adv gets a key and produces a digest d. In the second step, Aduz produces a sequence of elements and their openings. The adversary's goal is producing a digest where it can open probabilities that are not consistent with a single distribution Q. We require that for every PPTM Adv (Advv, Advz), for every (poly-time constructible) polynomial n) N +N
Pr key +- Gen(1",N)
(d,state) - Adv (key);
Q + Axt (key, 1 d. 1 17(N))
((z Fi. TT)..... (Imrs Pen: Im Tmm) )) +- Aduz(state).
3i E [m] s.l. (pr- + Q[xx-1) V (gi- + $
VCommit (Ix-, pi-, qi key, d, .T-) accept < (1()s)
We remark that the extractor needs to know explicit bound 17()s) on the success probability of the adversary, because the adversary can refuse to produce openings with but probability. The extractor needs to run it enough times to see the low-probability opening event. The construction of distribution-commiiment from CRHs is in Theorem B.4
Sampling from Q. Any distribution-commiteen scheme also allows for sampling from the com- mitted distribution Q follows. The receiver chooses random mass E (0, 1] and the sender opens the smallest x s.t. L [x] 2 a (using the commitment scheme's Open procedure).
Definition B.2 (Quantile function) For
a Quantile (p, key, d, aux) gets as input (cumulative) mass p (0, It outpuss the small- est x E [N] s.t. & ( 2 and opens x 's probabilities (i.e. the output of Open(z, key, d, aux)) say that Quantile's output valid if μ ((fo(xx)Q(a))) ( and VCommit accepts the probabilities and the proof.
Intribatiio-commiinee
scheme,
Remark B.3 (Sampling from Q) By construction, for honest sender and a uniformly random E (0, 1), running Quantile on input i produces random sample x ~ Q and the output is always valid. We sometimes refer to this the distribution commitment's ' sampling procedure.
18

---

Published as a conference paper at ICLR 2025
For security, the binding property of the commitment scheme means that cheating sender can either fail the Quantile procedure, or produce the appropriate element by Q. In particular, consider a receiver who runs the sampling procedure, immediately rejects invalid outputs and runs some additional tests on x's where the output was valid. The success probability of the cheating sender in passing whatever tests the receiver runs can be upper bounded (up to negligible terms) by the success probability of a sender who always produces oulputs by Q
Theorem B.4 cnnstribution-commitetn from CRH) Assuming the existence of a CRH family (see Definition A.9. there exists distribution-comiiinee scheme as per Definition B.
The runtime for producing the digest is N- poly(xx, The runtime for the Openftunctinallly is poly(k, . l))(N)) in the RAM model.
See the construction overview in Section 2.1 The details of the proof for Theorem B.4 follow.
Committing. The receiver chooses a hash function h from a CRH family (as per Definition A.9 and the sender commits to the distribution Q over [A] by constructing a full binary tree with N leaves (w.loo.g. we assume N is a power of 2, otherwise we use padding). Each node in the tree has a probability Pa and a label l, as follows.
1. for i E [M]. taking to be the i-th leaf in the tree, its probability and its label equal Q[i.. 2. for each internal node e with children u and w, its probability pa is defined to be the sum of the probabilities of its children. Its label includes its probability and hash of the labels its children, i.e. L. = (pe. h(&,, )
Note that the probability of each internal node is the sum of probabilities of leaves in its sub-tree, and thus the probability of the root should be 1.
The digest d is the label of the root of the binary tree. The receiver checks that its probability is (otherwise it rejects immediately). The auxiliary information (to be used in opening) is the entire binary tree (the probabilities and labels of all nodes).
Opening and verifying. To open the probability of a leaf i E [M], let S. be the set of all nodes on the path from the root to the i-th leaf and their siblings. The revealed pdf probability is the probability of the i-th leaf itself. The edf is the sum of the i-th leaf's probability, and the probabilities of all internal nodes in S, that are left-children of their parent. The proof π includes the labels of all nodes in S..
Verification proceeds as follows: for each internal node v in S, with revealed label (pr, y) and children u and we the verifier checks that pr: = (pw, + Pw)) and that y luluu f.) It also checks that the revealed pdf is the probability of the i-th leaf and that the revealed cdf is the sum of its probabilities and the probabilities of nodes in S. that are left-children
The extractor. The extractor runs the given adversary Adv₂ poly((1/n(<))), N) times, It sees a polynomial collection of opened elements x; E [N] (across all the runs), and in each opening sees labels for internal nodes of the tree. Let V be the collection of nodes (internal nodes and leaves) whose labels passed the consistency test (at least once over all the executions of Adv): namely, all nodes on the path from them to the root (and their siblings) passed the probability-consisti test and the lahel-consistency test. If there are nodes in V whose labels were opened differently in different executions, then the extractor fails (say it outputs a canonical distribution Q). Looking ahead, this shouldn't 't happen because it means that Adu; found hash collision. Otherwise, the extractor assigns to each node in V the (unique) probability that was opened for it. Observe that since these probabilities are all unique (across executions of Adv2) and they pass the probability- consistency test, they are consistent with a global distribution Q as follows:
for each leaf u V corresponding to the element probability that was opened for v.
[N]. Q[i is set to the (unique)
for each internal node in V whose children (and thus also its entire subtree) are both not in V. let Pa be the (unique) probability that was assigned to v. Let L, be the set of leaves in o's subtree. Then for each leaf in Ter, corresponding to element i [[i] Po/ T.ol-
19

---

Published as a conference paper at ICLR 2025
By construction, the extractor's output Q is distribution over [N] (the probabilities sum to 1).
Proof of binding. The collision-resistanee of h guarantees that in all the runs of Adez, including the runs of the extractor and the subsequent "critical" run, there is no node whose label is opened in two different ways (except with negligible probability). Thus, so long as the openings in the critical run are only for nodes for which the extractor also saw a successful opening, then the distribution Q is well defined and consistent with all of Advz's 's answers. The only freedom the adversary has is refusing to open certain nodes in the extractor's oracle calls, but then successfully opening them in the "critical" run in the security game. Of course, the adversary operates identically in the extractor's runs and in the critical run. Fixing the output of Adv' (and conditioning on no collisions), for any node where there is at least a (1/ ( probability that Adv₂ opens it correctly. the extractor will observe a correct opening w.h.p. over its poly(1/1), N) runs. Taking union bound over the adversary's s m I N openings in its critical run, the probability that it opens a node that wasn't 't seen by the extractor smaller than 7). Security follows.
C INTERACTIVE ARGUMENT FOR DISTRIBUTION PROPERTIES
C.I THE VERIFIED DISTRIBUTION ORACLE PROTOCOL
Proposition C.1 /Verified distribution oracle protocol] Assuming the existence of a CRH family (see Desinition A.9.) given domain size parameter N E N, distance parameter E (0, 1), black-box sample access to a distribution D over domain [N), and a randomized L(N)-time Turing Machine with oracle sample access D, called query generator machine G (N, e). there exists a protocol between an honest verifier and prover such that the following holds:
Completeness. If the prover is honest, then at the end of the interaction = (xx))()))))))))( for all x SA G (N,e), and the verifier accepts with all but negligible probability.
Soundness. For every poly-time prover strategy P", with all but negligible probabil- ity: either the verifier rejects; or there exists some distribution Q over [N] such that Srv(D.Q) < and qu = (2) for all x E SA-
The verifier runtime, D-sample complexity, and the communication complexity of the protocol are all ō (VN/2+ + +(N)) Honest prover runs time (oN)pol)(
Consider the following protocols:
Verified Distribution Oracle Protocol
Input:
Domain size parameter N E N, security parameter x E N, distance parameter E (0, 1).
Black-box sample access distribution 1) over domain [N], and a query generator ma- chine, randomized ((N )-time Turing Machine CN(Nee with oracle sample access to D, that outputs SA C [.V]
The honest prover also gets as input an explicit description of a distribution Q over [N] such that (D, Q) S
Goal: for every I E SA, obtain de such there exists a distribution Q over domain [N] that satisfies STv(D, @) S and = (z). Notations: Let Gen, Dig, Open, Vcommit be parts of commitment scheme, as defined in Defini- tion B.I
1. Establishing verified query access to distribution Q, close to D:
(a) V: generate key Gen (1*; N). and send key to the prover.
20

---

Published as a conference paper at ICLR 2025
(b) P: rum Dig(key, Q), and obtain digest d and auxiliary information aux. Send d to the
verifier.
(c) V-P: the verifier draws () samples according to the process described Remark
B.3 For every I drawn by this process, the prover provides Pa. = ((x), qu - ((x)
and proof TT. The verifier rejects unless Voommit (I, Pa, 9z, key, d, πx) accepts for all the samples.
(d) V-P: interactively run the identity tester from Corollary D.4 over d in the follow- ing sense: use the samples and their probability acquired in the previous step; and whenever the tester queries Q[xr], the verifier sends æ to the prover, that replies with
Qr - =Q[x] and Pz ((x),, obtained from Open(x, key, d, aux). The verifier runs Commma (z, Pa: qu key, d, Rw), and rejects if the algorithm rejects. Reject if the tester rejected.
2. Querying Q: (a) V: SΛ = GD(N,e), and send it to the prover.
(b) P: for every x: E SA, run Open(æ, key, d, aux), and send Pa, Ir and Tr to V.
(c) V: If for all SA, Veommit (I, Pa, qu key, d, Tx) didn't reject, the verifier accepts
and outputs {zz, 9x) 2 E SA).
We argue that the protocol above satisfies the conditions of Proposition C.I and then continue to show how this protocol can be levaraged to verify label-invariant distribution properties and lan- guages that admit IAP.
Proof: the protocol is complete. By Theorem B.4 the commitment scheme used in Protocol C. satisfies the conditions of Definition B.1 Thus, assuming the prover is honest, with probability at least 7(K] for every (polytime constructible) polynomial n N N. for all x queried be the verifier it holds that Qs = Q(x). Since by assumption Syv(Q, D) S e, with all by negligible probability the tester accepts.
Proof: the protocol is Sound. By Theorem B.4 the commitment scheme used in Protocol C.1 satisfies the condition that with all but probability ((( for any (polytme constructible) polynomial
I-- + N, it holds that either the verifier rejects, or there exists distribution Q over domain [N] such that all the verifier queries in Protocol C.1 satisfy 92 =())).
By Corollary D.4 if &rv(D, > e, the tester that the verifier ran in Step (4) of Protocol C. fails
with all but negligible probability. And so, with overwhelming probability, either the verifier rejects, or outputs Oa. for all x E SA such that 9s = Q(x) for some distribution Q over domain [N] that satisfies Ōrv(D,Q) < e. Which concludes the soundness proof.
The following sections show how to leverage this protocol to verify the family of polylog( (N) r-approximately decidable label-invariant distribution properties (see Definition A.6). and p(N)- approximately decided properties (see Definition A.8
C.1.1 VERIHICATION OF GENERAL DISTRIBUTION PROPERTIES THROUGH IAPs
For distribution Q over domain [N]. we formally describe the representation of Q follows:
Construction C.2 [String representation of Q] Fix parameters N N, granularity parameter 7 E θ (zzz). and a distribution Q over domain [N] that is n-grauular. Let C [N] - [0,1]"
be an error correcting code of constant rate and relative distance 1o2 Define the representation
XX E 10,1) (N//1)) as follows: for every x E [N), denote by set to 2(x), and define X
(0, 1 mm the string defined by concatenating ba the string C(x) E {0, 1)m Set:
xac = =x N.C.C C B.C P.C o... C.C.
Q11 Q2
Q.N
We claim that this representation satisfies the following properties:
21

---

Published as a conference paper at ICLR 2025
Claim C.3 (Properties of Construction C.2) Let Q be n-granular distribution over [N], and
X be its representation as defined in Construction C.2 for b ((N and constant- error-correcting code C with relative distance at least 0.1. The following hold:
C,C can be simulated by query to Q's quantile function and one query Each query X to Q's edf.
For every distance parameter E (0, 1) and distribution Q' over domain [N] with repre- sentation x& ifvvvQQ Q' > then Ham (xn.C X c/10
Proof. Fix query E [m/n]_ Let Quantileq : [0, [N] be the function that for every E [0.
[N] such that the edf of Q. Φ2(=) Qfy E [N] y S z)) satisfies ((x) 2 p. Denote di = Quantile(i 1)). By construction, this implies that is somewhere inside the string Xn.C Q.g. as defined in Construction C.2 Next, we need to know where falls inside copy of C(q.). Again, by construction, this location is linner
outputs the smallest
0gg 1)/n) mod Finally, X7. (i) C'(g)) iinner Observe that in order to output the i'th query, we required one query to Quantileq and one query the edf of Q. This concludes te first item in the claim.
Moving to the second item, let Q' be as described the claim statement. Consider the strings X C.C Q Q' E 10, to be naturally associated with strings in the space {0, 1111/1/(mm) we
abuse the notation and for every fouter E [1/nn], Vinner E [m]]. write X2 [Bouters iinner] = X2 I
1 1) + iinerr). and define also Xy.C(i [Fouters -] {0, 13 be defined the substring of length m starting at location (fouter 17 1)
Since and Q' are of distance c, it must be that at least e-fraction j [1/n] satisfy:
xQ x - [j.
Since otherwise, it means that the distributions agree on all units of mass, besides fraction smaller than e, which implies that the distributions are e-close in diy-distance, Since x - X2 2 [j. -] both code words in C, they are constant Hamming least 1 We thus conclude that Ham (n. XT.C 2 c/10.
Definition C.4 (The 8 tolerantt language of distribution property 11) Let 11 be some distribution property, and let n(N) = ((N-2) a granularity function. Fix a constant rate and distance 10
1 ECC family, such that CN [N] [m(N)]. We define the tolerant language of II to be
LT = (LII,N) such that:
{xai 1Iv(),1IN) S {
Claim C.5 (Representation Decision Algorithm) For every N N. let m(N) and r)(N) be as defined in Construction C.2 Every distribution property II that p(N) (aNaapprxximmttely decided in poly(N) time admits a poly-time algorithm Testa that takes as input N, a string X {0, 1/// and distance parameter d such that the following hold:
If there exists distribution Q such that X Testn accepts.
CnNN).CN and 8rr(Q, ITn) S 8 then XQ
If X doesn't encode distribution over domain [N]. there exists distribution Q such that X X (xN.).xx but (Iv(Q,IIn) 2 d, + p(N), then Testn rejects.
Proof. We define the algorithm:
T Testn checks that X m)/n encodes valid distribution Q, and rejects otherwise. This is done by considering X string over the space {0, 1/1 [x]] and that for every E [1/n], X(i, -) is codeword in C. Denote the decoding X(i, -) as Z;. It then checks that for all H, 1i 1, and rejects otherwise.
22

---

Published as a conference paper at ICLR 2025
Let Distn be as defined in Definition A.8 If the first test passed, Testn reconstructs the distribution Q that satisfies -QQ XD(N),C from the decoded string, and runs the Distn over Q with accuracy parameter p(N). If the output of Distn satisfies S dc + p(N), ), accepts, and otherwise, it rejects.
This concludes the proof. M
This immediately implies the following:
Corollary C.6 For every distribution property IT that p(N japproonoxy decided in poly(N), for any distance parameters 6e E (0,1), the promise problem of being in Li or yffar from it. is in P.
We thus provide the protocol behind Theorem [.1 Given p-approximately decided property II, and distance parameters de, 5y E (0, 1). Run Protocol C.1 with parameters c, 65-be p(N), and:
1. The prover sets Q = D.
2. After running Step (1) the protocol, run the communication phase of the IAP described in Theorem A. with distance parameter (6y=b²) and with respect the language G
and the string X X Obtain the queries to the string X7. through the IAP.
3. Set the query set for Q to be the elements in Q relevant to the locations queried by the protocol by the IAP in the representation X as explained in Claim C.3 (recall that that each such query to the representation can be simulated by queries provided by the distribution commitment scheme). Obtain verified openings from the prover,
4. Check that the IAP predicate accepts the queries, and reject otherwise.
We argue that this protocol satisfies the conditions of Theorem 1.1
Assume δτv D N S 8g. Since and D Q, and the prover is honest, the first stage of Protocol C.I doesn't result in rejection with overwhelming probability. Then, Since OTv(D, [lv) S de, and the queries to the representation string are correct according to D, from the completeness of the IAP, the verifier accepts with high probability.
Assume (Dv(D,Il 2 8f, then, assuming that Step (1) of Protocol C.I passed, then with overwhelming probability there exists a distribution Q such that δTv (Tv : D) S 54-6,
10
and all the prover's openings are according to Q. Then, since (rv(D, ITx) 2 8y. by the triangle inequality, holds that ÓTv(Q, Il) 2 6y that Ham (x xxx
5 By Claim C.3 this implies
10
1.
9(8 9(5,-5.)
69- for any Q that is 8, close to II,, and 20
10
10
so, by the soundness condition of the IAP, the predicate associated with rejects with high probability.
D THE IDENTITY TESTER
Theorem D.1 (Optimal Identity Tester Valiant & Valiant (0014); Goldreich (2020)) For every fixed distribution Q over (N), there exists an algorithm that given N, oracle access to Q, and black box sample access to a distribution D over domain [N], draws O(VNe-2) samples from D, and:
. Df = Q, the algorithm accepts with high probability.
. 1f Q) the algorithm rejects with high probability.
We give short review of the algorithm behind Theorem D.I and then explain how it is adapted to the setting of our result. We follow the algorithm described Goldreich (2020).
First, describe the algorithm under the following assumptions, that later remove:
23

---

Published as a conference paper at ICLR 2025
For some (VV, assume Q is -grannular, ie. for all E [N]. Q(x) =mz 1 where m E {0, .,..,,......... m}.
Assume Q has full support, Supp(Q) = [M]
Consider the set S ((x, [N] E [m=]), and for every [N] define the random variable (x( to be a uniformly chosen tuple from Sea = (( : E [m,]]-
Observe that the distribution over S obtained by first drawing
Q. and then selecting (x., j)
through (2(2) is the uniform distribution over S, since every (z,j) E S is sampled with probability
Q(x) [ myx I L. In other words, if D is distributed according to Q then (D = Us. In fact, this transformation preserves the total variation distance in the following sense: if ODv(D, Q) 6, then 6Tv (F) Us) = 6, since:
m
8TV (FQ(D).US
_ Σ
1
Σ
(Q(D)((E,)))
1 m mg
(1)
2 xE[N] JEm,
1 Σ
Σ
D
2
ma
mT
IE|N] jEimZ]
Σ
D(x)
ma
2
m
m
xE|N] mm
Σ
DD(x) Q(x)
(4)
2
m.
ZE[N] jE mm
1 Σ
D1(x) Q(x)
(5)
2
xE[N]
(D,
(6)
Note that we used the assumption that Q has full support on the second inequality when dividing by mz, and that is 1 --gramular on the fourth inequality to argue that Q(x)) mz for all x.
m
And so, testing that D = Q is reduced to testing that FQ(D) is uniform. Testing that samplable dis- tribution over domain of size m is uniform over the entire domain or c-far from it in dry-distance a fundamental well-researched problem in distribution testing, that is known to require O Pl//m-"3) samples (see Theorem A.4). Observe that DD) as a distribution over indeed samplable by first sampling x ~ D, querying Q(x), computing m. from it, and then sampling uniformly from [ma].
Removing assumptions over Q. We explain how to overcome the two assumptions given above:
Accounting for Q with partial support. Consider the distributions Q' = - (the distribution that assign E [N] the probability + and D' = 3 These two distributions are of full support, and satisfy 8Tv(D', Q') = TD, Q). Moreover, D' is samplable given that D is samplable, and Q' can be queried given oracle access to Q. Thus, assuming that Q' is 1 h--granular for some m = O(N), in order to test m whether D Q or &Tv(D,Q) > suffice to test that D' Q' or ÓTv Q') c/2, by sampling For ( D') and running the uniformity test as explained above, incurring only constant overhead in the sample complexity.
Accounting for non-granular Q. Assume that Q' as described above isn't 1 --granular m
for m ONN.. Set 6.V, and for every x E [N] define 0g (2((z)(() (/m) (1/m) We now define the distributions D and Q" over [N + 1]:
(((x))
- For every x E [")) = 0, Qx),, and Q" + +1) 11 EMEIN O2 Q'(x).
For every NN) D²))) 0z (1r),, and D" (x) = 1 -E Oz DD(xx)
24

---

Published as a conference paper at ICLR 2025
Note that if D' Q', then D" Q", and if 81v (D', c/2, then:
8TV (D" (0" =
Σ -x"x)-("(x))
(7)
xE[N+1]
Σ
02 (x)) Q'xx) ID" QN((N++))
(8)
2
ZE|N]
Σ FE|N]
0₂ 8=( Q(())
(9)
2
(10)
3
IV
39
(11)
Where the second to last inequality is justified by the fact that Q'(x) 2N for all a E [M] and thus, 02 2
('(x) 2 3- We conclude that in order to determine that D = Q or D is
1/6N
e-far from Q, suffice to to determine if D" =Q" or D" is e/3-far from Q". Observe that given oracle access to Q. 0g can be computed for every x E [N] so both oracle access to
Q" and sample access D" can be simulated. Lastly, assuming without loss of generality that N is divisible by 6, Q" is m -grranullar for m = 6.N.
I
Let Q" and D" be as defined the above proof. For every x E [N], querying Q" (x) can be be done by querying (zx) and computing Q'(x) and 0, from it. However, in order to query Q" 1), the tester needs to compute E.E(N] (1- 02) (x)), which involves querying N locations Q. increasing the tester's 's runtime significantly. The original setting for this tester was concerned with matching the D-sample complexity of the tester with the lower bound of Ω (VNe-2) regardless of the runtime of the tester. Since we want the runtime of the tester to also be of the same magnitude, we circumvent this obstacle by estimating Q" + 1) up to a very small error. This can be done with samples drawn according to Q, alongside the query access to Q. Concretely:
Claim D.2 Fix distribution Q over domain [N], and let Q" be defined in the proof of Theorem D.I There exists an algorithm with oracle access to Q that upon obtaining O(e samples from Q, approximates (N + 1) up to additive error of (E²) with high probability.
We prove Claim D.2
Consider the following algorithm: it draws 8 = 0(E -4) samples according to Q, and for every sample xy drawn, it queries Qzx;), computes Q'(x:) [Q(x)))+ 2N and then, computes 1 Oz;
1 Q' (x)/(//2) (//N) It then outputs Σiebs (1 - [z,)z,) Q'(x))(()..))))))))(()))
(())
Observe that Q"(N + 1) ExeINy (1 - 0,) Qz) E [1 0g). Since the random variable
(1 0z,) can only obtain values in the interval (0, 1). by Hoeffding's Inequality:
1 Σ Pr
(1-
Q" N
1 < 2e
22/e
20/6"
And so, since took O) the algorithm described above provides approximation of Q"(N + 1) up to additive error e² with high probability.
Remark D.3 An e² additive approximation of QN + 1) suffices for the purpose of the algorithm described in the proof of Theorem D.I since it only effects the estimated size of the set S by multiplicative factor of é. However, this doesn't 't effect the uniformity tester. The reader reffered Cannone Canonne (2015) for further detail.
Therefore, using samples from Q estimate Q" 1), conclude the following:
25

---

Published as a conference paper at ICLR 2025
Corollary D.4 For every fixed distribution Q over [N], there exists an algorithu that given pa- rameter N, oracle access to Q, as well as sample access to Q, and black box sample access to distribution over domain [N], draws O(yNE samples from D. (E (E=*) samples from Q, and:
If =Q, the algorithm accepts with high probability.
ÖT D2 Q) > 6, the algorithm rejects with high probability.
The runtime of the algorithm (
Remark D.5 We only consider such that w (/N),/4), since every smaller value provable required super linear sample complexity, and O(c 2 O(vNe=). Also note that the completeness and soundness error be made negligibly by amplification through repetition polylog(NN) times.
26


Reviews:
[{"review_id": "mBFaK8PZgd", "reviewer": "Reviewer_m7Ct", "summary": "This paper falls in the area of distribution testing. In the standard setting of distribution testing, we have given sample access to an unknown distribution $D$ over a finite domain of size $N$ and the goal is to design algorithm that tests whether $D$ is $\\epsilon_1$-close (in some distance measure such as total variation distance) to a distribution  satisfying a property ${\\mathcal P}$ or $D$ is $\\epsilon_2$-far from any distribution that satisfies ${\\mathcal P}$. It is known that in this (known as the tolerant testing) setting, the sample complexity, even for very simple properties such as testing uniformity, is close to $\\theta(N/\\epsilon^2)$. \n\nThe paper argues that if we take certain interactive proof system approach the sample complexity can be improved by a quadratic factor. In this model, there is a prover and a verifier both of them having sample access to the unknown distribution. An interactive proof is a communication protocol between prover and verifier so that: \n\n1. if the distribution $D$ is close to having the property ${\\mathcal P}$, then an efficient prover can convince the verifier of this fact with high probability (completeness). \n\n2. However, If $D$ is far from having the property ${\\mathcal P}$, then no polynomial time prover can make the verifier accept with non-negligible probability (soundness). \n\nThe main result is that for any ${\\mathit efficiently}$ decidable property, there is such a proof system (under standard cryptographic assumptions) with verifiers sample and time complexities $\\tilde{O}(\\sqrt{N}/\\epsilon^2)$. This is a quadratic improvement from the standard scenario. The paper also discusses several extensions.", "questions": "I do not have any specific questions regarding the content, and I appreciate the results presented in the paper. However, I strongly recommend that the authors focus on improving the clarity and formalism in the presentation. While the core ideas are interesting, the current exposition may be challenging for readers who are not deeply familiar with this specific line of research.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The model and the results are interesting and believe that  this paper will be of interest to those working in the property testing area.", "weaknesses": "The paper appears to have been hastily written. Even some of the main definitions are relegated to the appendix. The main body of the paper primarily discusses rough ideas, with only one formal statement of the main result. Furthermore, there are no formal proofs provided (I cannot see them in the appendix also). While the main ideas are described clearly, the paper lacks the level of technical clarity that the reviewer would expect from an ICLR submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "laQOMx0ab4", "reviewer": "Reviewer_JVRG", "summary": "This paper gives efficient interactive verification protocols for distribution property testing. Specifically, the goal is to design a communication protocol between a prover and a verifier, such that the verifier, given sample access to an unknown distribution $D$ and the ability to make certain queries to the prover, is able to verify the membership of $D$ in a class/property of probability distributions. A tolerant verifier parametrized by $\\varepsilon_c$ and $\\varepsilon_f$ is guaranteed to verify membership of distributions that are at most  $\\varepsilon_c$-close in total variation distance to some distribution in the class and to reject  $\\varepsilon_f$-far distributions and the sample complexity depends on the difference $\\rho=\\varepsilon_f-\\varepsilon_c$. \n\nSpecifically, the protocol uses $\\tilde{O}(\\sqrt{N}/\\rho^2)$ samples from $D$, which matches that of prior work by [Chiesa and Gur 2018] and is quadratically better than lower bounds for standalone (i.e without a prover) tolerant distribution testing problems. The main novelty of this work lies in the quadratic improvement of the protocol’s communication complexity and running time over prior work. This is achieved using cryptographic collision resistant hash functions. The prover is assumed to have knowledge of the distribution $D$ up to sufficient accuracy and forced to commit to a distribution as part of the protocol without having to transmit an explicit description of it. This fact along with the use of the PCP theorem are the tools that make it possible for the communication complexity and running time to be significantly reduced. The protocol works by first having the prover send a short digest $d$ of the distribution $D$ using cryptographic hashing to commit to it for the answers to future queries. Subsequently, the verifier uses queries to run an interactive argument of proximity (IAP) in order to check if the bit string representation of the committed distribution is accepted by a turing machine that decides closeness to the property.   \n\nThe above protocol provides a unified way of dealing with any class/property of distributions that is decidable in polynomial time and since there is no sampling involved in that step, the sample complexity is the same for every such property.", "questions": "Could your techniques be applied to property testing where there are no samples involved (e.g graph property testing) by addressing the queries to the prover? \nCan you elaborate more on the benefit of this work to the community of ICLR in particular?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper cleverly combines tools from cryptography with interactive proof protocols to achieve sublinear communication complexity and running time for a fundamental class of problems.", "weaknesses": "In my opinion, the results, techniques used in the paper as well as the lack of experimental evaluation, would make it a better fit for a theoretical computer science conference.\n\n\nMinor comments:\n\n\n-Line 20: “should possible”->“should be possible” \n-Line 125-128: This does not seem to give a lower bound for the distance $\\delta$. You need to run tolerant verification with $\\varepsilon_c=\\delta-\\rho$ and $\\varepsilon_f=\\delta$ as well.\n-Line  184: It seems that the dependence on the parameter $\\varepsilon$ is missing from the sample complexity that is cited here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vx3nxtP0wC", "reviewer": "Reviewer_K79e", "summary": "This paper considers a setting where an untrusted prover and verifier both have sample access to an unknown distribution, and the prover wishes to convince the verifier that the distribution has some property. The prover does so using an interactive protocol, which is efficient in the sense that the communication complexity and sample complexity of the verifier are low. In particular, their protocol applies to some properties where testing (from scratch, without a prover) provably requires a higher sample complexity than that of the verifier.\n\tTheir protocol has two components. The first is a distribution-commitment, a new cryptographic primitive that allows a prover to succinctly commit to a distribution and verifiably answer natural queries, such as the probability of any element or the cdf. The second component is a reduction to interactive arguments of proximity, using this distribution commitment. That is, they show a protocol where the prover commits to the distribution. The verifier then tests the correctness of this commitment by sampling from the unknown distribution. The prover and verifier then engage in an interactive argument of proximity to test that the committed distribution indeed has the claimed property.", "questions": "How does one ensure that the committed cdf values are consistent with the committed probabilities?\n\nHow do distribution commitments relate to random variable commitments ([BGKW24])? Can they be used to construct random variable commitments?\n\n[BGKW24]: https://eprint.iacr.org/2024/938.pdf", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper shows an original and strong result, that a large class of distributional properties can be proven efficiently. It does so using interesting techniques; in particular, it introduces the distribution commitment which appears to be a useful primitive for future protocols. The distribution commitment allows them to leverage existing work on IAPs to construct their protocol. The ideas are elegant and clearly presented.", "weaknesses": "While the high-level ideas are presented clearly, the details are a bit lost due to the submission format. For example, there is no proof of their distribution oracle construction. It would be helpful to explain how their commitment ensures that the prover doesn’t commit to conflicting probabilities and cdf values.\n\nDistribution commitments seem even closer to vector commitments than cryptographic accumulators. It would be nice to see this discussed in 2.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JdDKRWr1Kj", "reviewer": "Reviewer_zrGv", "summary": "The paper introduces an interactive protocol for the verification of distribution properties, computationally sound. The protocol is performed between a verifier and an untrusted prover, where both have sampling access to some unknown distribution. The major contribution of this work is an argument system that can be used in verifying any property such that, given the full description of a distribution, one may approximately compute its distance from the property in polynomial time.The protocol has a communication complexity and verifier runtime of roughly  O( N​/eps^2 ) which is nearly optimal. This yields a quadratic speedup over prior approaches with quasi-linear sample complexity. The authors also provide applications to testing properties like monotonicity and juntas and extend their approach to properties in NP.", "questions": "Can the authors elaborate more on how the distribution commitment scheme actually prevents a cheating prover from misleading the verifier? \n\nHow will the choice of collision-resistant hash function eVect the performance and security of the protocol? \n\nAre there scalability issues when this protocol is applied to distributions with very large support sizes, and how might they be addressed?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Quadratic Speedup: The protocol provides a quadratic improvement over existing works, closing the sample complexity and runtime of the verifier to near optimality.\n\nBroad Applicability: It can verify a wide range of properties, including those that are not label-invariant, expanding the scope beyond previous work.\n\nDetailed Explanation: The paper offers clear explanations and technical overviews, making complex concepts accessible.\n\nExtensions and Applications: The authors illustrate how the protocol can be applied to many different properties and extend it to properties in NP, showing its versatility", "weaknesses": "Cryptographic Assumptions: The reliance on collision-resistant hash functions means that the soundness of the protocol is predicated upon some cryptographic assumptions, which may not be valid in every setting.\n\nLimited Practical Evaluation: The paper does not include any empirical results or practical demonstrations showing the protocol's performance on real data.\n\nOmitted Technical Details: The book omits some proofs and detailed constructions, like the full proof of Theorem B.4, and such an omission could impair complete understanding of the implementation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BJVpozm9EL", "reviewer": "Reviewer_ZJhC", "summary": "This paper considers the problem of verifying whether an unknown discrete distribution satisfies certain properties with a prover. The authors show that it is possible to verify a wide class of properties using a sublinear number of samples and running time. Without a prover, even testing some properties requires quasi-linear samples, which is a big improvement.", "questions": "Seet the first point in weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The problem of verifying a claim from another party is theoretically important and has practical applications.\n2. The authors achieve sublinear time, communication, and sample complexity for the verifier. In contrast, (tolerant) testing without a prover often requires quasi-linear samples. This is a substantial improvement over previous works. It is also an interesting theoretical result that shows verifying with a prover can be easier than doing testing without a prover.\n3. The problem formulation and results are very general and can be applied to many testing and learning problems.", "weaknesses": "1. Is the $\\tilde{O}(N)$ sample complexity for an honest prover also optimal?\n2. I prefer to have some key technical results and lemmas when presenting the technical steps.\n3. Theorem B.4. does not have full proof. What is its role in the result?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QE3IYGjpzo", "reviewer": "Reviewer_BGYN", "summary": "A recurring theme in theoretical computer science is that *verifying* an answer is often (computationally) easier than deriving the answer *from scratch*. This work illustrates this principle in the context of distribution testing. Let $\\mathcal{P}$ be a distribution property (i.e., set of distributions) such that with full knowledge of a given distribution $Q$, I can efficiently decide whether $Q \\in \\mathcal{P}$ or not. The paper’s main result shows that If someone *else* (”Prover”) has already put in extensive effort to fully identify a distribution $Q$ and I (”Verifier”) only have sample-access to $Q$, then I can test whether $Q$ satisfies the property $\\mathcal{P}$ with far less effort by engaging in an interactive protocol with the Prover. This verification is feasible even without any trust in the Prover and is strictly more efficient than the naive solution of the Prover simply sending over the full representation of $Q$.\n\nThe lack of trust in the Prover introduces several challenges. Let $\\tilde{Q}$ be the representation of the “distribution” on $[N]$ the Prover holds (quotations since the $\\tilde{Q}$ may not even be a valid distribution) and let $Q$ be a distribution on $[N]$ which the Verifier has only sample-access to. Here, the support size $N$ is the index with respect to which computational complexity is defined. In the absence of trust, the Verifier must check that 1) $\\tilde{Q}$ is a valid distribution and 2) $\\tilde{Q} = Q$. The second part uses the identity (a.k.a. goodness-of-fit) testing algorithm by Goldreich (2017) which has $\\sqrt{N}$ sample complexity. The Prover’s overall honesty in responding to Verifier’s queries is enforced through cryptographic commitment schemes, whose security is based on collision-resistant hash functions.\n\nOnce the Verifier checks that $\\tilde{Q} = Q$, then it remains to check that $\\tilde{Q} \\in \\mathcal{P}$. The deterministic decision $Q \\in \\mathcal{P}$ potentially requires poly($N$) time to compute. However, PCPs allow the Verifier to probabilistically check this much more efficiently, incurring only poly($\\log(N)$) additional communication cost for checking $\\tilde{Q} \\in \\mathcal{P}$ on top of the $\\sqrt{N}$ needed for identity testing.", "questions": "1. In Theorem 1.1, it seems like the sample complexity of the Verifier is $\\sqrt{N} \\cdot \\mathrm{poly}(\\kappa)$, but since we assume $\\kappa$ to be polynomially related to $N$, shouldn't sample complexity technically be $N^{1/2+c}$ for an arbitrary constant $c > 0$?\n\n2. What properties are *not* efficiently decidable? For example, are the following properties efficiently decidable (or even decidable at all)?\n    - (Uncomputable?) A sequence $(Q_N)$ which is uniform over a subset $S_N \\subseteq [N]$ where $j \\in S_N$ if and only if $M_j$ halts on input $N$, where $M_j$ is the $j$-th Turing machine enumerated by a universal Turing machine.\n    - (Inefficient?) A class of \"perfectly balanced\" distributions $\\mathcal{P}_N$, where $Q \\in \\mathcal{P}_N$ if there exists a subset $S \\subset [N]$ such that $Q(S) = Q([N]\\setminus S)$.\n\n3. What is a \"poly-time\" ERM algorithm? What is the polynomial with respect to?\n\n4. What is the \"efficiently decidable property\" that corresponds to the ERM verification setup (line 198)? What is the role of the hypothesis class $\\mathcal{H}$?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I believe this is a well-executed work with solid contributions for reasons discussed below.\n\n**Exceptional exposition.** The paper is impeccably written, providing a highly accessible explanation of non-trivial techniques while maintaining full formality. Papers at the intersection of computational complexity and learning theory frequently overlook considerations related to input representation and finite precision. This paper addresses all such subtleties explicitly and cleanly. Moreover, the high-level ideas for the interactive protocol are easy to follow as they are presented in a modularized manner, with each module highlighting key insights.\n\n**Novelty of ideas.** The use of cryptographic commitment schemes to prevent cheating of the Prover seems like a natural approach and may be standard in the field, although I am not familiar with the interactive proofs literature. However, combining commitment schemes with identity testing to achieve $\\sqrt{N}$ sample complexity appears novel since it involves distilling the *essence* of previously known identity testing algorithms. As shown in Section 2 (line 301), the authors analyze what the identity tester *actually* needs to know about $Q$, rather than its full truth table. Furthermore, this interactive protocol works for *any efficiently decidable* distribution property which is  a substantial improvement over previous work.", "weaknesses": "Further discussion on the following aspects would be beneficial for the paper.\n\n**Distribution properties that are *not* efficiently decidable.** To develop intuition for efficiently decidable distribution properties, it would be good to understand what properties are *not* efficiently decidable. Also, if we restrict to singleton sets, what is an example of a (sequence of) distributions the TV distance to which is not efficiently computable? Few candidates that come to mind are\n\n- (Uncomputable?) A sequence $(Q_N)$ which is uniform over a subset $S_N \\subseteq [N]$ where $j \\in S_N$ if and only if $M_j$ halts on input $N$, where $M_j$ is the $j$-th Turing machine enumerated by a universal Turing machine.\n\n- (Inefficient?) A class of \"perfectly balanced\" distributions $\\mathcal{P}_N$, where $Q \\in \\mathcal{P}_N$ if there exists a subset $S \\subset [N]$ such that $Q(S) = Q([N]\\setminus S)$.\n\n**Verifying ERMs (line 198)?** The term \"poly-time\" ERM algorithm is unclear. What is the polynomial with respect to? Is it the support size $N$? The notion of a \"poly-time\" ERM algorithm sounds weird to me since for most interesting hypothesis classes, ERM is not known to be poly time (in $n = \\log N$ where we identify $[N] = \\\\{0,1\\\\}^n$). What is the \"efficiently decidable property\" that corresponds to this ERM verification setup? What is the role of the hypothesis class $\\mathcal{H}$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7j2I2slTw9", "reviewer": "Reviewer_2JWS", "summary": "The paper describes how a verifier can check that a distribution which they can sample from has (up to small error) a certain (polynomial time verifiable) property in O(sqrt(n)polylog(n)) time with support from an untrusted prover that already knows the distribution. The protocol consists of the prover commiting to (an approximation of) the true distribution, then proving to the verifier that this matches what they are sampling in a way that only needs O(sqrt(n)) samples, finally the prover proves that the committed distribution has (or rather is clsoe in TV distance to having) the desired property.", "questions": "See the questions embedded in the weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The problem is natural and the solution is clean and at least in some senses optimal.\n\nThe presentation does a good job of clearly explaining what it does ( althoguh a lot of details are left out of the main part).", "weaknesses": "I would like to have mroe details on the identity testing part, I'm guessing that this is not particularly novel to this work but there should at least be a reference in the section describing it to where more information can be found (edit: I've found the reference in sec 2.0 but a reminder of it later would be good as well). It would also be good to have more explanation of how it works, e.g. to what extent do the queries to the committed distribution depend on samples? would it be possible to make that part non-interactive with the FS heuristic at the cost of assuming your CRH is an RO?\n\nThis paper is largely jsut a combination of powerful ideas from previous papers, though there is some non-trivial work in choosing the represntations for the distributions to allow the application of the previous work.\n\nThis work is unlikely to work well in practice due to the constants being very big in some of the used tools (e.e. PCP theorem).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)