WorksComputer Science
Products of Distinguisher Hulls
Abstract
The distinguisher hull of two distributions is the convex hull of the pairs of acceptance probabilities of tests in a specified class. We study its behavior under independent products for size-bounded Boolean circuits. We derive a geometric consequence of Dwork and Tankala's supersimulator theorem (FOCS 2026), giving a substantially different proof of approximate product containment for distinguisher hulls. In particular, our construction uses nonadaptive sampling in place of adaptive score corrections.
Introduction
A distinguishing advantage records one width of a testing region. The entire region retains the trade-off between the two acceptance probabilities. We call its convexified, computationally restricted version a distinguisher hull. With unrestricted tests it is the Lorenz hull of the two probability measures.
We give a direct geometric proof of quantitative containment for distinguisher hulls under independent products. This containment also follows, with the same asymptotic circuit bound and an increase in only one factor’s budget, from the supersimulator lemma of Dwork and Tankala [5]. Our proof uses planar segment decompositions and sampling of sections of a given test. All section queries are fixed by independently sampled anchors before their answers are evaluated. In the regularity construction, tests are instead selected through corrections depending on the current residual. This is a distinction in construction: after selection, the sections in a specialized regularity proof can also be queried nonadaptively, with sequential score processing. We do not claim an oracle-adaptivity separation. A reverse inclusion, obtained from a regularity-based score construction, makes points in the geometric product approximately attainable with larger circuits. Iteration gives statements for repeated sampling and products of different pairs of distributions.
Computational distinguishability under products has been studied by Halevi and Rabin [2], Geier [3], Marcussen, Putterman, and Vadhan [4], and Dwork and Tankala [5]. The underlying statistical geometry appears as privacy regions and trade-off functions in Kairouz, Oh, and Viswanath [6] and Dong, Roth, and Su [7]. We use the Lorenz-hull product of Steinberger and Zhang [1], defined through products of vector measures. The attainability argument also specializes regularity and supersimulation methods [8, 5]. Thus our emphasis is the geometric formulation and direct containment proof, rather than an improvement of their circuit bounds. Appendix § 11 derives both bounds from their machinery and gives the remaining comparisons. Appendix § 12 compares the constructions and optimizes the constants in the regularity derivation.
Definitions and forward containment
Use a fixed universal fan-in-two Boolean circuit basis, with constants and complemented wires free. Define the size- distinguisher hull by
For finite input spaces this is a polygon. Constants and complements make it centrally symmetric about , containing and contained in . Its lower-boundary edge vectors are nonnegative and sum to , so it is a Lorenz hull of a pair of probability measures. For finitely supported signed measures, write . We use the coordinate-wise Lorenz product of Steinberger and Zhang [1], characterized by
Their results establish that the product is independent of the representing measures, associative, commutative, distributive over Minkowski sums, and inclusion-preserving. Write .
Theorem 1. There is an absolute constant such that, for every , , and distributions and on two finite bit-string spaces,
Consequently, for a pair ,
Only one factor’s circuit budget grows in (1). Swapping the two inputs gives the analogous statement with the other factor enlarged instead. No efficient sampling algorithm for any of the distributions is assumed. Sampling below is an averaging argument over hardwired anchors. For each fixed joint test, all calls to its sections use anchors selected independently of the input and of the query answers. The postprocessing may depend nonuniformly on the second factor’s hull. This is not an assertion that the reduction, its anchors, or its geometric data can be found efficiently. We first give the core argument with a less economical lookup-table bound, then prove the geometric implementation that yields the stated size bound.
The geometric factorization
If a probability Lorenz polygon has nonnegative segment generators summing to , then
Here the sums are Minkowski sums. The second identity follows from distributivity and the identity [1].
Lemma 2 (Factorization through a polygon). Let be a probability Lorenz polygon, let be as in (2), and let be a finite-valued statistic of an input . For each possible value of , choose coefficients and put
Suppose that, for every , the acceptance pair of belongs to . Then
Proof. The displayed point equals
Apply (2) to its summands.
The coefficients need not be computed together. Each coefficient may have its own circuit. This is permitted by the definition of a computational hull and is the reason the number of generators of need not enter the first bound.
The core sampling proof
Fix one size- Boolean circuit and put . For every fixed , its section has size at most , so
Draw anchors independently from and independently from . Define
For every fixed ,
Let be Euclidean projection onto . For every point of the grid, choose coefficients in representing in (2). For fixed anchors and fixed , the function is a bounded real-valued lookup function of the two counts.
Every such function is a convex combination of Boolean lookup functions:
There are only finitely many distinct Boolean functions in this integral. Each uses copies of , two population counts, and a lookup on possibilities. Its size is . Thus its acceptance pair, and that of the real-valued coefficient, belong to .
Lemma 2 shows that for every fixed anchor choice,
The average over anchors remains in this convex set. Projection onto a closed convex set does not increase distance from a point of that set, so (3) and Cauchy–Schwarz give
Integrating its first coordinate under and its second under yields
In a section-query model with arbitrary processing of the answers, this core proof uses just nonadaptive section queries and has error . For ordinary circuits, it already proves a direct containment bound with . Nothing in this argument replaces the original distributions. The following two elementary geometric observations remove the large lookup-table term.
Implementing the coefficients economically
Lemma 3 (A small inscribed polygon). For a probability Lorenz polygon and , there is a probability Lorenz polygon with vertices such that
Proof. The lower boundary from to is coordinate-wise nondecreasing and has total length two. Select its endpoints and additional points so that successive selected points are at most apart in boundary length. Take the convex hull of these points and their reflections through . This gives with vertices. Every point of either boundary chain of is within Euclidean distance of a selected point. Every point of is a convex combination of boundary points, so the same distance bound holds throughout . The polygon has the required symmetry, endpoints and nonnegative lower edge vectors, and is therefore a probability Lorenz polygon.
Lemma 4 (Coefficient threshold circuits). Let be a probability Lorenz polygon with vertices and nonnegative generators . There are functions such that
and, on the grid , every threshold is computable from the two binary integers by a Boolean circuit of size . The bound is independent of the precision of the polygon’s real coordinates.
Proof. First suppose has nonempty interior. At each vertex choose coefficients in representing that vertex, and assign coefficient to every generator at the center . Triangulate by joining to its successive vertices, and interpolate each coefficient affinely on every triangle. This gives continuous functions on with values in and .
Extend these functions by Euclidean projection. Outside the polygon, projection onto the relative interior of an edge is affine on its outward normal strip; projection onto a vertex is constant on its outward normal cone. Thus each extended coefficient is affine on regions. Each region is the intersection of at most three affine half-planes: an interior triangle, an edge strip, or a vertex cone. A coefficient threshold is consequently a union of sets, each described by at most four affine half-plane inequalities.
On the finite integer grid , any affine half-plane dichotomy can be represented exactly with integer coefficients of magnitude . Here is an elementary justification. Slightly shift the defining threshold so that it strictly separates its two grid classes, and rescale to give all points margin at least one. The resulting system has rows and right-hand side one. Restrict to independent coordinate directions if its column rank is less than three. The feasible polyhedron then has no lines and has a vertex. At that vertex, Cramer’s rule applied to at most three independent active constraints gives rational coefficients whose numerators have magnitude at most . Clearing the determinant denominator gives integer coefficients with that bound and preserves every classification. Constant dichotomies need no argument.
Each resulting half-plane test uses arithmetic on -bit integers. Shift-and-add multiplication by hardwired integers and comparison take Boolean gates. Intersect and unite the region predicates to obtain the claimed bound. Shared boundaries cause no problem because the coefficient functions agree there.
If is degenerate, it is the diagonal segment from to . Set every coefficient equal to the clipped affine function . Since , this represents the projection onto the diagonal segment, and each coefficient threshold satisfies the same bound.
Proof of the stated circuit bound
Proof of Theorem 1. Repeat the core proof for a fixed , but set
and use from Lemma 3. Replace projection onto by projection onto , with the coefficients from Lemma 4. Since Euclidean projection is nonexpansive,
Taking the anchor expectation bounds this by .
For a fixed anchor choice, each Boolean coefficient-threshold test now has size
The counts cost gates: a balanced addition tree has total size . The last equality in Eq. (6) uses and boundedness of on .
Choose the universal constant in large enough for these circuits. Equation (4) puts every coefficient’s acceptance pair in . Lemma 2, followed by averaging over anchors, therefore gives a point in
within distance of the acceptance pair of . The inclusion uses the Lorenz product’s inclusion preservation. Finally, is convex, so the same inclusion holds for the convex hull of all size- tests .
Attainability
Theorem 5. For , , and , there is a universal constant such that
where
In particular, .
Attainability here is in the convex hull of circuit acceptance pairs. It does not mean that every interior point is attained by one deterministic circuit. All constructions are nonuniform existence arguments; neither efficient samplers nor algorithms for finding the circuits are assumed.
A score whose hull approximately dominates the given hull
The construction below is a specialization of the supersimulator method of Dwork and Tankala [5 Lemma 2.6], in the regularity tradition of Trevisan, Tulsiani, and Vadhan [8]. We include the short potential argument and its translation into hull containment.
Lemma 6. For each integer and pair , there is a circuit computing a score , encoded by its integer numerator, of size
such that, writing for the ordinary Lorenz hull of its two output laws,
Proof. Let and on the support of . Set elsewhere. Then and . Put and start with .
For the current score, consider every size- Boolean test and every threshold test . If any such test satisfies
choose one, let be the sign of this expectation, and replace by
The potential obeys
Clipping can only improve the squared distance to . Since , fewer than updates are possible. At termination,
holds both for all size- tests and for every threshold of the final score.
The score remains on the stated grid. An update appends either a size- circuit or a comparison of the current integer score with a hardwired integer, followed by a conditional increment or decrement and saturation. It costs gates. Earlier score circuits are shared, not copied. This proves the size bound, including for updates that use a threshold of the current score. Finding a violating test is not asserted to be efficient.
It remains to translate (7) into hull domination. Normalize a mixed-sign support direction to , with and . For every size- test ,
The threshold has acceptance pair in , and
Thus the support functions satisfy . Both hulls are centrally symmetric about , so the same bound holds in the opposite mixed-sign directions. In same-sign directions their support functions agree, since both are in and contain . By homogeneity the error in any direction is at most , proving the inclusion.
Only residual correlations with Boolean tests and score thresholds are used. There is no need here to control the residual separately on every score level, or to prove indistinguishability of replacement distributions.
Two elementary product facts
Lemma 7. If are probability Lorenz hulls and , then
Proof. For every probability Lorenz hull , . Indeed, is the sum of the four axis segments generated by , , , . The projection of on either coordinate axis is . Distributivity and the segment product identity give the assertion. Replace the factors one at a time, using inclusion preservation and this identity. Every product of the other, unreplaced or replaced, factors is a probability Lorenz hull. The errors therefore add. No product of two error boxes is needed.
Lemma 8. Suppose are deterministic statistics taking values in , each computable by a circuit of size at most , with outputs encoded as binary indices. Let . For ,
where, for ,
Proof. Round each of the output probability vectors to a probability vector with denominator . Taking floors and distributing the missing units gives total variation error at most in each vector. Each of the two product laws consequently changes by at most in total variation.
For the rounded laws, the product hull is a finite zonotope. Every vertex is attained by a likelihood-ratio threshold test, with constants and complements included. On the score tuple , such a test compares the two products of hardwired integer probability numerators
The relevant likelihood ratios are ratios of integers at most . Any threshold cut between distinct ratios can therefore be specified by a rational threshold with numerator and denominator of bits (use a mediant between consecutive ratios). Endpoint cuts, zero probabilities, and infinite ratios are handled by zero tests and constants. At a supporting edge, including or excluding an entire tied ratio class gives its endpoints; convexification supplies the edge.
Each lookup of costs gates, by decoding the score and selecting hardwired bits. Balanced schoolbook multiplication computes the two products with gates; the final integer comparison, including multiplication by threshold constants, has the same bound. Adding the statistic circuits gives .
To approximate an arbitrary point of the actual product hull, use its acceptance function under the rounded laws first. Its two coordinates change by at most . Express that rounded acceptance pair as a convex combination of vertices of the rounded hull, and implement their threshold circuits as above. Evaluating this same convex combination under the actual laws changes the coordinates by at most another . Its acceptance pair is in , proving the assertion.
Products of arbitrarily many factors
Proof of Theorem 5. Set . Apply Lemma 6 separately to each factor. Lemma 7 gives
Apply Lemma 8 with , , and . Then and its circuit bound is
The first term absorbs the others for , . The two error boxes sum to .
Together with Theorem 1, this gives the following two directions, at different circuit budgets:
For the first inclusion, iterate Theorem 1 with error , leaving the remaining block at budget at every step. The identity used in Lemma 7 makes these errors additive. This is not a same-budget Hausdorff approximation or a claim of sharp overhead.
Relation to prior results
This appendix records implications between specific statements. A different formulation or proof does not by itself establish a strict strengthening or incomparability. In particular, the hull-valued nature of our conclusions alone does not separate them from the proxy constructions below.
Testing regions and trade-off functions. For unrestricted tests, write
For finite distributions this equals the convex hull of the acceptance pairs of Boolean tests. In type-I/type-II error coordinates, the corresponding region is the image of under . Kairouz–Oh–Viswanath call the region for a fixed pair of output distributions a privacy region [6 Eq. (3)]. Dong–Roth–Su instead use its optimal boundary, the trade-off function
Their Appendix A also discusses the equivalent testing-region representation, restricted to tests at least as good as random guessing. Central symmetry recovers the other half of the full region. Their product is defined by
They prove that this product is well-defined, associative and monotone [7 Definition 3.1 and Appendix D]. For pairs of probability measures, it represents the coordinate-wise Lorenz product through its boundary. The statistical product geometry is prior work. The circuit bounds in the present paper concern its computational restriction.
An asymmetric hull consequence of MPV. We use the corrected version of the partition theorem in [4 Theorem 3.1]. Given and the size- test class, it supplies proxies and a statistic taking values, such that each original is -indistinguishable from its proxy,
and the two proxies have the same conditional distribution on each cell . Null cells can be assigned arbitrary conditional laws. Set and , so that
Fix a size- joint test . Replacing its first input by the respective proxy changes each acceptance probability by at most : fixing leaves a size- test of , and one then averages over . For each cell let . Its acceptance pair under belongs to , since it is a convex combination of acceptance pairs of size- sections. The proxy joint acceptance pair is
If computing costs gates, every Boolean function of costs gates by a finite lookup. With this budget denoted by , , giving
The right-hand side is convex, so the argument extends from individual tests to the entire hull. This proves that both the shape conclusion and the asymmetric form follow from MPV’s partition theorem, with its resource cost.
For input length on a full bit-string domain, the corrected bound in that theorem gives
Theorem 1 gives the smaller bound for the same containment. This comparison is with the explicit derivation (8); it is not a claim that all of MPV’s conclusions follow with improved parameters. Their theorem also constructs proxies with properties not supplied by our forward proof.
The same partition theorem yields qualitative attainability. Computational closeness and the common conditional laws imply . Lemma 7 transfers this inclusion to products. The statistic has a finite range, so Lemma 8 implements the product hull with polynomial overhead. Hence polynomial-overhead attainability itself is also a consequence of the partition construction, even though its bounds differ from ours.
The reverse bound from Dwork–Tankala. The score step of our proof follows from the general supersimulator lemma [5 Lemma 2.6]. With and , choose the growing test family
where denotes the size- Boolean tests. The lemma supplies whose residual correlations with every member of are at most . These are precisely the two conditions used in Lemma 6.
For reciprocal-integer error, their construction uses signed updates with a fixed step of order . The running sum can be stored as an integer with bits, and its clipped value has possible outputs. At each step the added test is either a size- circuit or a threshold of the existing score. Sharing that score circuit gives total size
Their use of clipping the accumulated sum, rather than clipping after every update as above, does not change this circuit accounting or the final residual guarantee. The support-function argument in Lemma 6 and Lemmas 7–8 then give Theorem 5 with the stated order of circuit size. Thus the reverse theorem is a geometric application of their machinery; the score construction is not an independent strengthening of it.
The forward bound from Dwork–Tankala. Theorem 1, including its asymmetric circuit budgets, also follows from their supersimulator lemma. We give the derivation since it is not stated in this geometric form in [5]. Write , , , and , assigning an arbitrary value where the denominator vanishes. Apply the lemma with the growing family consisting of all size- tests, all thresholds of , and their complements. For , the resulting score satisfies
for every such test. The shared-counter implementation described above computes each threshold and its complement with size
One can take reciprocal-integer within a constant factor of any specified tolerance. Since the constant test is included, . Define probability measures
For every test in the family, replacing by these proxies changes each acceptance probability by at most : replacing by costs , and normalizing costs at most another . The proxy likelihood ratio is monotone in . Their statistical hull is therefore the convex hull of the acceptance pairs of score thresholds, their complements, and constants. Consequently
Now fix a size- joint test and put . Conditional on any score value of positive -mass, the proxies have the common conditional law whenever that conditioning event has positive proxy mass. Averaging over this law gives a convex combination of size- tests of , hence an acceptance pair in . Decomposing into the segments given by its score masses shows that the proxy joint acceptance pair lies in . The original joint pair differs from it by at most in each coordinate, since every section has size at most . Lemma 7 now gives
It remains to remove the apparent logarithmic overhead. Take of order , with . If , then already. Otherwise, fix again and discard gates not connected to its output. A fan-in-two circuit with at most gates reads at most distinct input bits, so it reads at most bits of . Let record those bits. The section acceptance pair depends only on . Choose a segment decomposition of separately for each value of . Each coefficient threshold is a Boolean function of at most bits and has a truth-table circuit of size . Lemma 2 therefore gives exact containment for this joint test with that first-factor budget. Since , this budget is at most . Taking convex hulls completes the derivation of Theorem 1 with its stated bound in both regimes.
Scalar product bounds. Geier’s two-factor theorem bounds computational distinguishing advantage by plus an error decreasing exponentially with a reduction parameter, when is fixed [3 Theorem 3.1]. The corresponding circuit overhead has logarithmic dependence on inverse error, apart from input-length costs. The quadratic inverse-error dependence of our forward bound does not recover that efficiency. Geier also treats uniform reductions, whereas our statements concern nonuniform circuits.
The hull retains information absent from these two scalar inputs. For example, the probability pairs
both have total variation distance , but their squares have total variation distances and , respectively. Thus the same scalar product bound applies to both while their hull products differ. This certifies loss of information in the scalar summary, not a theorem that no further use of Geier’s methods can yield shape-sensitive bounds. Halevi–Rabin [2] additionally study sequential interactive protocols; our independent-product statements do not address that setting.
Fehr–Vaudenay [9] obtain statistical repeated-sampling inequalities under additional information about the distributions. Such inequalities can be applied to the probability experiments representing the hull factors in our forward theorem. They provide bounds on the product’s thickness, with at most additional distinguishing advantage from an error box. This is a way to combine the results, rather than an incomparability claim.
Structure of the reductions and explicit constants
Selection and evaluation. For a fixed joint test , the sampling proof draws anchors independently from and . Each coefficient circuit queries the same fixed list of sections and then processes their answers. The queries are nonadaptive, and their selection uses no residual tests. The construction remains nonuniform: the hull geometry is supplied as hardwired data, and averaging over anchors establishes containment in a convex hull rather than a deterministic efficient procedure for choosing anchors.
The regularity proof below selects a test using its correlation with the current residual and updates a score. Both the selection and the score construction are sequential. This does not imply adaptive oracle queries during evaluation of the final circuit. Once the selected small circuits are fixed, they can be evaluated in parallel; their outputs feed the successive score updates. Moreover, for a fixed one can restrict the small-test family to its sections : the proof below uses only convex combinations of those sections. This version also has a fixed list of section queries at evaluation time, although it selects that list by residual-dependent corrections rather than independent sampling. The structural distinction is therefore independent sampling versus residual-dependent selection, not a proved separation between adaptive and nonadaptive oracle reductions. No lower bound on the parallel depth of the regularity implementation is asserted.
Printed constants and constants of the deduction. Dwork–Tankala’s Lemmas 2.4 and 2.6 print the update bound , with step size [5]. Their main product theorem gives circuit costs in asymptotic notation. Combining the printed update bound with the normalized-proxy deduction in Appendix § 11, whose error is , gives updates at . The number belongs to this deduction; it is not a bound printed in their paper for a hull theorem.
Two elementary tightenings reduce it. Initializing at bounds by . Their prefix-sum proof then gives updates, without changing the construction. This sharpens the estimate for this initialization, not their statement for an arbitrary prescribed . Next, normalization of the proxies is unnecessary: use and . Each tested expectation changes by at most , and the proxy hull is within of the computational hull by the threshold argument. Although these measures need not be probabilities, multiplication by the unchanged probability hull still preserves the error box, by distributivity and . The total error is therefore . Together these observations give updates.
Projecting after every update, instead of clipping the accumulated sum, gives a further factor of two: with step , a violated residual test reduces squared error by more than . This gives updates from initialization , or for error . This modification preserves the residual guarantee but changes the structured-sum representation specified in their lemma. The following specialization improves the error accounting as well. Its numerical bound is derived here from their regularity method; it is not an explicitly stated bound in [5].
Proposition 9. For , the asymmetric containment
holds with
More precisely, the construction uses updates when , each containing at most one size- circuit, where
Terms with zero denominator are zero. When , no updates are needed. The remaining circuit cost is .
Proof. Put , , , and on the support of . Set and initialize . For each current score , consider the growing family
This includes constant thresholds. Every member has absolute value at most one. If violates , choose its correlation sign and set
The potential satisfies
Initially the potential is . Thus the number of updates is strictly less than if positive, and the final score satisfies
The same estimate holds if and are independently replaced by convex combinations of their respective classes.
Each update evaluates one size- test and a threshold of the preceding score, then conditionally increments, decrements, or leaves the score unchanged, with clipping. The preceding score circuit is shared. There is no precision assumption on : every score value is of the form , with and an integer . Store the choice of and the integer . Clipping resets this representation to an endpoint. Threshold comparisons use hardwired integer cutoffs for each of the three choices of . Consequently each update costs at most gates, and a final threshold costs gates.
To prove containment, fix a size- joint test and set
Every lies in , and each scalar function is a convex combination of size- tests of . Consider a support direction with , . Write as above, discarding zero generators. For choose
Each is a threshold, or a constant, and maximizes over . In particular, at ,
Writing , the point
belongs to , since each threshold of has size at most . Let . Subtracting the two support evaluations yields
The last step uses (9): and are convex combinations of score thresholds, with weights summing to one. Taking the supremum over proves the support inequality in this quadrant. Both hulls are centrally symmetric about , which gives the opposite mixed-sign quadrant. In same-sign directions the support functions agree, since both hulls lie in and contain . Homogeneity now gives the error in every direction , which is precisely containment up to .
Comparison with sampling. Give a fraction of the sampling proof’s error budget to polygon approximation. Its explicit cost is
For fixed , its coefficient of is , approaching one as decreases. The optimized regularity proof already has coefficient one (up to integer rounding), but its displayed arithmetic overhead is rather than . These bounds therefore do not establish a uniform total-gate advantage in either direction. They also do not prove that coefficient one is optimal for either approach.
The apparent coefficients 128, 8, and 4 in successively tightened proxy-based derivations are not barriers. The change to differences of tests avoids estimating two residual correlations separately and reduces the final support error from to ; the update count falls by a factor of four. Neither proxy normalization nor proxy measures are needed in this optimized specialization. For reference, the successive bounds on the number of updates, each containing at most one size- circuit, are
| Derivation | Hull error | Update bound at error |
| Printed lemma and normalized-proxy deduction | ||
| Initialization 1/2 and unnormalized proxies | ||
| Projection after every update | ||
| Differences of tests, Proposition 9 |
Table 1.
These are bounds from particular derivations, excluding arithmetic overhead, not necessary costs or a constant-factor separation from the published results. The small-circuit truth-table argument in Appendix § 11 still recovers the uniform bound when the logarithmic arithmetic term would dominate.
References
- [1]J. Steinberger and Z. Zhang. A Product on Lorenz Hulls, Zonoids, and Vector Measure Ranges. ArXiv preprint, 2023. https://arxiv.org/abs/2309.09790.
- [2]S. Halevi and T. Rabin. Degradation and Amplification of Computational Hardness. TCC, 2008. https://eprint.iacr.org/2008/102.DOI
- [3]N. Geier. A Tight Computational Indistinguishability Bound for Product Distributions. TCC, 2022. https://eprint.iacr.org/2021/1274.DOI
- [4]C. Marcussen, A. Putterman, and S. Vadhan. Characterizing the Distinguishability of Product Distributions through Multicalibration. CCC, 2025. Comparisons use corrected arXiv version 5, October 27, 2025. https://arxiv.org/abs/2412.03562v5.
- [5]C. Dwork and P. Tankala. Efficient and Private Property Testing via Indistinguishability. FOCS, 2026. Comparisons use arXiv version 2, April 6, 2026. https://arxiv.org/abs/2511.03653v2.
- [6]P. Kairouz, S. Oh, and P. Viswanath. The Composition Theorem for Differential Privacy. ICML, 2015. https://proceedings.mlr.press/v37/kairouz15.html.
- [7]J. Dong, A. Roth, and W. J. Su. Gaussian Differential Privacy. Journal of the Royal Statistical Society, Series B, 84(1):3–37, 2022. Definition and appendix numbering refer to the arXiv version. https://arxiv.org/abs/1905.02383.
- [8]L. Trevisan, M. Tulsiani, and S. Vadhan. Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. CCC, 2009. https://people.seas.harvard.edu/~salil/research/regularity-ccc09.pdf.DOI
- [9]S. Fehr and S. Vaudenay. Sublinear Bounds on the Distinguishing Advantage for Multiple Samples. IWSEC, 2020. https://ir.cwi.nl/pub/30130/30130.pdf.DOI