betaFeedback

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-ss distinguisher hull by

Hs(P,Q)=conv⁡{(EPf,EQf):f is a Boolean circuit of size at most s}.H_s(P,Q)=\operatorname{conv}\{(\mathbb{E}_P f,\mathbb{E}_Q f): f\text{ is a Boolean circuit of size at most }s\}.

For finite input spaces this is a polygon. Constants and complements make it centrally symmetric about (1/2,1/2)(1/2,1/2), containing (0,0),(1,1)(0,0),(1,1) and contained in [0,1]2[0,1]^2. Its lower-boundary edge vectors are nonnegative and sum to (1,1)(1,1), so it is a Lorenz hull of a pair of probability measures. For finitely supported signed measures, write LH⁡(P,Q)={(∑xP(x)f(x),∑xQ(x)f(x)):0≤f≤1}\operatorname{LH}(P,Q)=\{(\sum_x P(x)f(x),\sum_x Q(x)f(x)):0\le f\le1\}. We use the coordinate-wise Lorenz product of Steinberger and Zhang [1], characterized by

LH⁡(P,Q)⊙LH⁡(P′,Q′)=LH⁡(P⊗P′,Q⊗Q′).\operatorname{LH}(P,Q)\mathbin{\odot}\operatorname{LH}(P',Q')=\operatorname{LH}(P\otimes P',Q\otimes Q').

Their results establish that the product is independent of the representing measures, associative, commutative, distributive over Minkowski sums, and inclusion-preserving. Write Eη=[−η,η]2E_\eta=[-\eta,\eta]^2.

Theorem 1. There is an absolute constant CC such that, for every s≥0s\ge0, 0<η≤10<\eta\le1, and distributions PX,QXP_X,Q_X and PY,QYP_Y,Q_Y on two finite bit-string spaces,

Hs(PX⊗PY,QX⊗QY)⊆HS(PX,QX)⊙Hs(PY,QY)+[−η,η]2,S=⌈C(s+1)η−2⌉.(1)H_s(P_X\otimes P_Y,Q_X\otimes Q_Y)\subseteq H_S(P_X,Q_X)\mathbin{\odot}H_s(P_Y,Q_Y)+[-\eta,\eta]^2,\qquad S=\lceil C(s+1)\eta^{-2}\rceil. \tag*{(1)}

Consequently, for a pair P,QP,Q,

Hs(P⊗2,Q⊗2)⊆HS(P,Q)⊙2+[−η,η]2.H_s(P^{\otimes2},Q^{\otimes2})\subseteq H_S(P,Q)^{\odot2}+[-\eta,\eta]^2.

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 LL has nonnegative segment generators v1,…,vrv_1,\ldots,v_r summing to (1,1)(1,1), then

L=∑j=1r[0,vj],K⊙L=∑j=1rdiag⁡(vj)K.(2)L=\sum_{j=1}^{r}[0,v_j],\qquad K\mathbin{\odot}L=\sum_{j=1}^{r}\operatorname{diag}(v_j)K. \tag*{(2)}

Here the sums are Minkowski sums. The second identity follows from distributivity and the identity K⊙[0,v]=diag⁡(v)KK\mathbin{\odot}[0,v]=\operatorname{diag}(v)K [1].

Lemma 2 (Factorization through a polygon). Let KK be a probability Lorenz polygon, let LL be as in (2), and let FF be a finite-valued statistic of an input xx. For each possible value tt of FF, choose coefficients λj(t)∈[0,1]\lambda_j(t)\in[0,1] and put

R(t)=∑jvjλj(t)∈L.R(t)=\sum_j v_j\lambda_j(t)\in L.

Suppose that, for every jj, the acceptance pair of x↦λj(F(x))x\mapsto\lambda_j(F(x)) belongs to KK. Then

(EPXR1(F(X)),EQXR2(F(X)))∈K⊙L.(\mathbb{E}_{P_X}R_1(F(X)),\mathbb{E}_{Q_X}R_2(F(X)))\in K\mathbin{\odot}L.

Proof. The displayed point equals

∑jdiag⁡(vj)(EPXλj(F(X)),EQXλj(F(X))).\sum_j \operatorname{diag}(v_j)\left(\mathbb{E}_{P_X}\lambda_j(F(X)),\mathbb{E}_{Q_X}\lambda_j(F(X))\right).

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 LL need not enter the first bound.

The core sampling proof

Fix one size-ss Boolean circuit D(x,y)D(x,y) and put L=Hs(PY,QY)L=H_s(P_Y,Q_Y). For every fixed xx, its section y↦D(x,y)y\mapsto D(x,y) has size at most ss, so

r(x)=(EPYD(x,Y),EQYD(x,Y))∈L.r(x)=\left(\mathbb{E}_{P_Y}D(x,Y),\mathbb{E}_{Q_Y}D(x,Y)\right)\in L.

Draw anchors Y1,…,YmY_1,\ldots,Y_m independently from PYP_Y and Z1,…,ZmZ_1,\ldots,Z_m independently from QYQ_Y. Define

r^(x)=(1m∑i=1mD(x,Yi),1m∑i=1mD(x,Zi)).\widehat{r}(x)=\left(\frac{1}{m}\sum_{i=1}^{m}D(x,Y_i),\frac{1}{m}\sum_{i=1}^{m}D(x,Z_i)\right).

For every fixed xx,

Eanchors∥r^(x)−r(x)∥22≤12m.(3)\mathbb{E}_{\mathrm{anchors}}\lVert\widehat{r}(x)-r(x)\rVert_2^2\leq\frac{1}{2m}. \tag*{(3)}

Let πL\pi_L be Euclidean projection onto LL. For every point tt of the (m+1)×(m+1)(m+1)\times(m+1) grid, choose coefficients in [0,1][0,1] representing πL(t)\pi_L(t) in (2). For fixed anchors and fixed jj, the function x↦λj(r^(x))x\mapsto\lambda_j(\widehat{r}(x)) is a bounded real-valued lookup function of the two counts.

Every such function is a convex combination of Boolean lookup functions:

λj(r^(x))=∫011{λj(r^(x))≥u} du.(4)\lambda_j(\widehat{r}(x))=\int_0^1\mathbf{1}\{\lambda_j(\widehat{r}(x))\geq u\}\,du. \tag*{(4)}

There are only finitely many distinct Boolean functions in this integral. Each uses 2m2m copies of DD, two population counts, and a lookup on (m+1)2(m+1)^2 possibilities. Its size is O(m(s+1)+m2)O(m(s+1)+m^2). Thus its acceptance pair, and that of the real-valued coefficient, belong to K=HO(m(s+1)+m2)(PX,QX)K=H_{O(m(s+1)+m^2)}(P_X,Q_X).

Lemma 2 shows that for every fixed anchor choice,

wanchors=(EPX(πLr^)1,EQX(πLr^)2)∈K⊙L.w_{\mathrm{anchors}}=\left(\mathbb{E}_{P_X}(\pi_L\widehat{r})_1,\mathbb{E}_{Q_X}(\pi_L\widehat{r})_2\right)\in K\odot L.

The average ww 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

Eanchors∥πLr^(x)−r(x)∥2≤12m.\mathbb{E}_{\mathrm{anchors}}\lVert\pi_L\widehat{r}(x)-r(x)\rVert_2\leq\frac{1}{\sqrt{2m}}.

Integrating its first coordinate under PXP_X and its second under QXQ_X yields

∥w−(EPX⊗PYD,EQX⊗QYD)∥∞≤12m.(5)\left\lVert w-\left(\mathbb{E}_{P_X\otimes P_Y}D,\mathbb{E}_{Q_X\otimes Q_Y}D\right)\right\rVert_\infty\leq\frac{1}{\sqrt{2m}}. \tag*{(5)}

In a section-query model with arbitrary processing of the answers, this core proof uses just 2m2m nonadaptive section queries and has error 1/2m1/\sqrt{2m}. For ordinary circuits, it already proves a direct containment bound with S=O((s+1)η−2+η−4)S=O((s+1)\eta^{-2}+\eta^{-4}). 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 LL and 0<δ≤10 < \delta\le1, there is a probability Lorenz polygon L′⊆LL' \subseteq L with O(1/δ)O(1/\delta) vertices such that

sup⁡r∈Ldist⁡2(r,L′)≤δ.\sup_{r \in L} \operatorname{dist}_{2}(r,L') \le\delta.

Proof. The lower boundary from (0,0)(0,0) to (1,1)(1,1) is coordinate-wise nondecreasing and has total ℓ1\ell_1 length two. Select its endpoints and additional points so that successive selected points are at most δ\delta apart in boundary ℓ1\ell_1 length. Take the convex hull of these points and their reflections through (1/2,1/2)(1/2,1/2). This gives L′⊆LL' \subseteq L with O(1/δ)O(1/\delta) vertices. Every point of either boundary chain of LL is within Euclidean distance δ\delta of a selected point. Every point of LL is a convex combination of boundary points, so the same distance bound holds throughout LL. The polygon L′L' has the required symmetry, endpoints and nonnegative lower edge vectors, and is therefore a probability Lorenz polygon.

Lemma 4 (Coefficient threshold circuits). Let L′L' be a probability Lorenz polygon with MM vertices and nonnegative generators vjv_j. There are functions λj:R2→[0,1]\lambda_j:\mathbb{R}^{2} \to[0,1] such that

πL′(t)=∑jvjλj(t),\pi_{L'}(t) = \sum_j v_j\lambda_j(t),

and, on the grid t=(k/m,ℓ/m)t=(k/m,\ell/m), every threshold 1{λj(t)≥u}\mathbb{1}\{\lambda_j(t) \ge u\} is computable from the two binary integers k,ℓk,\ell by a Boolean circuit of size O(Mlog⁡2(m+2))O(M\log^2(m+2)). The bound is independent of the precision of the polygon’s real coordinates.

Proof. First suppose L′L' has nonempty interior. At each vertex choose coefficients in [0,1][0,1] representing that vertex, and assign coefficient 1/21/2 to every generator at the center o=(1/2,1/2)o=(1/2,1/2). Triangulate L′L' by joining oo to its successive vertices, and interpolate each coefficient affinely on every triangle. This gives continuous functions on L′L' with values in [0,1][0,1] and ∑jvjλj(t)=t\sum_j v_j\lambda_j(t)=t.

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 O(M)O(M) 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 O(M)O(M) sets, each described by at most four affine half-plane inequalities.

On the finite integer grid {0,…,m}2\{0,\ldots,m\}^{2}, any affine half-plane dichotomy can be represented exactly with integer coefficients of magnitude O(m2)O(m^2). 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 ±(k,ℓ,1)\pm(k,\ell,1) 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 6max⁡(1,m)26\max(1,m)^2. 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 O(log⁡(m+2))O(\log(m+2))-bit integers. Shift-and-add multiplication by hardwired integers and comparison take O(log⁡2(m+2))O(\log^2(m+2)) 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 L′L' is degenerate, it is the diagonal segment from (0,0)(0,0) to (1,1)(1,1). Set every coefficient equal to the clipped affine function λj(t)=min⁡(1,max⁡(0,(t1+t2)/2))\lambda_j(t) = \min(1,\max(0,(t_1+t_2)/2)). Since ∑jvj=(1,1)\sum_j v_j = (1,1), 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 DD, but set

δ=η/2,m=⌈2η−2⌉,L=Hs(PY,QY),\delta= \eta/2,\qquad m = \lceil2\eta^{-2}\rceil,\qquad L = H_s(P_Y,Q_Y),

and use L′⊆LL' \subseteq L from Lemma 3. Replace projection onto LL by projection onto L′L', with the coefficients from Lemma 4. Since Euclidean projection is nonexpansive,

∥πL′r^(x)−r(x)∥2≤∥r^(x)−r(x)∥2+∥πL′r(x)−r(x)∥2.\lVert\pi_{L'}\hat r(x)-r(x)\rVert_2 \le\lVert\hat r(x)-r(x)\rVert_2 + \lVert\pi_{L'}r(x)-r(x)\rVert_2.

Taking the anchor expectation bounds this by 1/2m+δ≤η1/\sqrt{2m}+\delta\le\eta.

For a fixed anchor choice, each Boolean coefficient-threshold test now has size

2ms+O(m+η−1log⁡2(m+2))=O((s+1)η−2).(6)2ms+O\left(m+\eta^{-1}\log^2(m+2)\right)=O\left((s+1)\eta^{-2}\right). \tag*{(6)}

The counts cost O(m)O(m) gates: a balanced addition tree has total size O(∑k≥1mk/2k)=O(m)O\left(\sum_{k\ge1}mk/2^k\right)=O(m). The last equality in Eq. (6) uses m=Θ(η−2)m=\Theta(\eta^{-2}) and boundedness of ηlog⁡2(2+η−2)\eta\log^2(2+\eta^{-2}) on (0,1](0,1].

Choose the universal constant in SS large enough for these circuits. Equation (4) puts every coefficient’s acceptance pair in K=HS(PX,QX)K=H_S(P_X,Q_X). Lemma 2, followed by averaging over anchors, therefore gives a point in

K⊙L′⊆K⊙LK\odot L'\subseteq K\odot L

within ℓ∞\ell_\infty distance η\eta of the acceptance pair of DD. The inclusion uses the Lorenz product’s inclusion preservation. Finally, K⊙L+[−η,η]2K\odot L+[-\eta,\eta]^2 is convex, so the same inclusion holds for the convex hull of all size-ss tests DD.

Attainability

Theorem 5. For n≥2n\ge2, s≥0s\ge0, and 0<η≤10<\eta\le1, there is a universal constant CC such that

⨀i=1nHs(Pi,Qi)⊆HR(⨂i=1nPi,⨂i=1nQi)+Eη,\bigodot_{i=1}^{n} H_s(P_i,Q_i)\subseteq H_R\left(\bigotimes_{i=1}^{n}P_i,\bigotimes_{i=1}^{n}Q_i\right)+E_\eta,

where

R=⌈Cn3η2(s+log⁡2nη)⌉.R=\left\lceil C\frac{n^3}{\eta^2}\left(s+\log\frac{2n}{\eta}\right)\right\rceil.

In particular, Hs(P,Q)⊙n⊆HR(P⊗n,Q⊗n)+EηH_s(P,Q)^{\odot n}\subseteq H_R(P^{\otimes n},Q^{\otimes n})+E_\eta.

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 m≥1m \ge1 and pair P,QP,Q, there is a circuit computing a score p(x)∈{0,1/m,…,1}p(x) \in\{0,1/m,\ldots,1\}, encoded by its integer numerator, of size

T=O(m2(s+log⁡(m+2))),T = O\left(m^2(s+\log(m+2))\right),

such that, writing L=LH⁡(p∗P,p∗Q)L=\operatorname{LH}(p_*P,p_*Q) for the ordinary Lorenz hull of its two output laws,

Hs(P,Q)⊆L+E4/m.H_s(P,Q) \subseteq L+E_{4/m}.

Proof. Let μ=(P+Q)/2\mu=(P+Q)/2 and ρ(x)=Q(x)/(P(x)+Q(x))\rho(x)=Q(x)/(P(x)+Q(x)) on the support of μ\mu. Set ρ=0\rho=0 elsewhere. Then dQ=2ρ dμ\mathrm{d}Q=2\rho\,\mathrm{d}\mu and dP=2(1−ρ) dμ\mathrm{d}P=2(1-\rho)\,\mathrm{d}\mu. Put ε=1/m\varepsilon=1/m and start with p=0p=0.

For the current score, consider every size-ss Boolean test and every threshold test 1{p≥t}1\{p\ge t\}. If any such test ff satisfies

∣Eμ[(ρ−p)f]∣>ε,\left|\mathbb{E}_{\mu}[(\rho-p)f]\right|>\varepsilon,

choose one, let σ\sigma be the sign of this expectation, and replace pp by

p′=clip⁡[0,1](p+σεf).p'=\operatorname{clip}_{[0,1]}(p+\sigma\varepsilon f).

The potential Φ(p)=Eμ(ρ−p)2\Phi(p)=\mathbb{E}_{\mu}(\rho-p)^2 obeys

Φ(p′)≤Φ(p)−2ε∣Eμ[(ρ−p)f]∣+ε2Eμf<Φ(p)−ε2.\Phi(p')\le\Phi(p)-2\varepsilon\left|\mathbb{E}_{\mu}[(\rho-p)f]\right|+\varepsilon^2\mathbb{E}_{\mu}f<\Phi(p)-\varepsilon^2.

Clipping can only improve the squared distance to ρ∈[0,1]\rho\in[0,1]. Since 0≤Φ≤10\le\Phi\le1, fewer than m2m^2 updates are possible. At termination,

∣Eμ[(ρ−p)f]∣≤ε(7)\left|\mathbb{E}_{\mu}[(\rho-p)f]\right|\le\varepsilon \tag*{(7)}

holds both for all size-ss tests and for every threshold of the final score.

The score remains on the stated grid. An update appends either a size-ss circuit or a comparison of the current integer score with a hardwired integer, followed by a conditional increment or decrement and saturation. It costs O(s+log⁡(m+2))O(s+\log(m+2)) 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 (−a,b)(-a,b), with a,b≥0a,b\ge0 and a+b=1a+b=1. For every size-ss test ff,

−aEPf+bEQf=2Eμ[(ρ−a)f]≤2Eμ[(p−a)+]+2ε.-a\mathbb{E}_{P}f+b\mathbb{E}_{Q}f=2\mathbb{E}_{\mu}[(\rho-a)f] \le2\mathbb{E}_{\mu}[(p-a)_+]+2\varepsilon.

The threshold g=1{p≥a}g=1\{p\ge a\} has acceptance pair in LL, and

−aEPg+bEQg=2Eμ[(p−a)+]+2Eμ[(ρ−p)g]≥2Eμ[(p−a)+]−2ε.-a\mathbb{E}_{P}g+b\mathbb{E}_{Q}g=2\mathbb{E}_{\mu}[(p-a)_+]+2\mathbb{E}_{\mu}[(\rho-p)g]\ge2\mathbb{E}_{\mu}[(p-a)_+]-2\varepsilon.

Thus the support functions satisfy hHs(−a,b)≤hL(−a,b)+4εh_{H_s}(-a,b)\le h_L(-a,b)+4\varepsilon. Both hulls are centrally symmetric about (1/2,1/2)(1/2,1/2), so the same bound holds in the opposite mixed-sign directions. In same-sign directions their support functions agree, since both are in [0,1]2[0,1]^2 and contain (0,0),(1,1)(0,0),(1,1). By homogeneity the error in any direction uu is at most 4ε∥u∥1=hE4ε(u)4\varepsilon\|u\|_1=h_{E_{4\varepsilon}}(u), proving the inclusion. □\square

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 Ki,LiK_i, L_i are probability Lorenz hulls and Ki⊆Li+EδiK_i \subseteq L_i + E_{\delta_i}, then

⨀iKi⊆⨀iLi+E∑iδi.\bigodot_i K_i \subseteq\bigodot_i L_i + E_{\sum_i \delta_i}.

Proof. For every probability Lorenz hull AA, A⊙Eδ=EδA \odot E_\delta= E_\delta. Indeed, EδE_\delta is the sum of the four axis segments generated by δe1\delta e_1, −δe1-\delta e_1, δe2\delta e_2, −δe2-\delta e_2. The projection of AA on either coordinate axis is [0,1][0,1]. 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 FiF_i are deterministic statistics taking values in {0,…,M−1}\{0,\ldots,M-1\}, each computable by a circuit of size at most TT, with outputs encoded as binary indices. Let Li=LH⁡((Fi)∗Pi,(Fi)∗Qi)L_i = \operatorname{LH}((F_i)_*P_i,(F_i)_*Q_i). For 0<γ≤10 < \gamma\le1,

⨀iLi⊆HU(⨂iPi,⨂iQi)+Eγ,\bigodot_i L_i \subseteq H_U\left(\bigotimes_i P_i,\bigotimes_i Q_i\right) + E_\gamma,

where, for N=⌈2nM/γ⌉N = \lceil2nM/\gamma\rceil,

U=O(nT+nMlog⁡(MN+2)+n2log⁡2(N+2)).U = O\left(nT + nM\log(MN+2) + n^2\log^2(N+2)\right).

Proof. Round each of the 2n2n output probability vectors to a probability vector with denominator NN. Taking floors and distributing the missing units gives total variation error at most M/N≤γ/(2n)M/N \le\gamma/(2n) in each vector. Each of the two product laws consequently changes by at most γ/2\gamma/2 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 z=(z1,…,zn)z=(z_1,\ldots,z_n), such a test compares the two products of hardwired integer probability numerators

A(z)=∏iai(zi),B(z)=∏ibi(zi),0≤ai(zi),bi(zi)≤N.A(z)=\prod_i a_i(z_i), \qquad B(z)=\prod_i b_i(z_i), \qquad0\le a_i(z_i),b_i(z_i)\le N.

The relevant likelihood ratios are ratios of integers at most NnN^n. Any threshold cut between distinct ratios can therefore be specified by a rational threshold with numerator and denominator of O(nlog⁡(N+2))O(n\log(N+2)) 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 ai,bia_i,b_i costs O(Mlog⁡(MN+2))O(M\log(MN+2)) gates, by decoding the score and selecting hardwired bits. Balanced schoolbook multiplication computes the two products with O(n2log⁡2(N+2))O(n^2\log^2(N+2)) gates; the final integer comparison, including multiplication by threshold constants, has the same bound. Adding the statistic circuits gives UU.

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 γ/2\gamma/2. 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 γ/2\gamma/2. Its acceptance pair is in HUH_U, proving the assertion.

Products of arbitrarily many factors

Proof of Theorem 5. Set m=⌈8n/η⌉m=\lceil8n/\eta\rceil. Apply Lemma 6 separately to each factor. Lemma 7 gives

⨀iHs(Pi,Qi)⊆⨀iLi+E4n/m⊆⨀iLi+Eη/2.\bigodot_i H_s(P_i,Q_i) \subseteq\bigodot_i L_i + E_{4n/m} \subseteq\bigodot_i L_i + E_{\eta/2}.

Apply Lemma 8 with M=m+1M=m+1, γ=η/2\gamma=\eta/2, and T=O(m2(s+log⁡(m+2)))T=O(m^2(s+\log(m+2))). Then N=O(n2/η2)N=O(n^2/\eta^2) and its circuit bound is

O(n3η2(s+log⁡2nη)+n2ηlog⁡2nη+n2log⁡22nη).O\left(\frac{n^3}{\eta^2}\left(s+\log\frac{2n}{\eta}\right)+\frac{n^2}{\eta}\log\frac{2n}{\eta}+n^2\log^2\frac{2n}{\eta}\right).

The first term absorbs the others for n≥2n\ge2, 0<η≤10<\eta\le1. The two error boxes sum to EηE_\eta.

Together with Theorem 1, this gives the following two directions, at different circuit budgets:

Hs(P⊗n,Q⊗n)⊆Hs(P,Q)⊙n+Eη,S=O((s+1)n2/η2),H_s(P^{\otimes n},Q^{\otimes n})\subseteq H_s(P,Q)^{\odot n}+E_\eta,\qquad S=O((s+1)n^2/\eta^2),
Hs(P,Q)⊙n⊆HR(P⊗n,Q⊗n)+Eη,R=O(n3η−2(s+log⁡(2n/η))).H_s(P,Q)^{\odot n}\subseteq H_R(P^{\otimes n},Q^{\otimes n})+E_\eta,\qquad R=O\left(n^3\eta^{-2}(s+\log(2n/\eta))\right).

For the first inclusion, iterate Theorem 1 with error η/(n−1)\eta/(n-1), leaving the remaining block at budget ss 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

H(P,Q)={(EPf,EQf):0≤f≤1}.H(P,Q)=\{(\mathbb{E}_P f,\mathbb{E}_Q f):0\le f\le1\}.

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 H(P,Q)H(P,Q) under (x,y)↦(x,1−y)(x,y)\mapsto(x,1-y). 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

T(P,Q)(α)=1−sup⁡{y:(x,y)∈H(P,Q), x≤α}.T(P,Q)(\alpha)=1-\sup\{y:(x,y)\in H(P,Q),\ x\le\alpha\}.

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

T(P,Q)⊗T(P′,Q′)=T(P⊗P′,Q⊗Q′).T(P,Q)\otimes T(P',Q')=T(P\otimes P',Q\otimes Q').

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 P,QP,Q and the size-ss test class, it supplies proxies P~,Q~\widetilde{P},\widetilde{Q} and a statistic pp taking MM values, such that each original is ε\varepsilon-indistinguishable from its proxy,

p∗P=p∗P~,p∗Q=p∗Q~,p_*P=p_*\widetilde{P},\qquad p_*Q=p_*\widetilde{Q},

and the two proxies have the same conditional distribution νj\nu_j on each cell p=jp=j. Null cells can be assigned arbitrary conditional laws. Set L=LH⁡(p∗P,p∗Q)L=\operatorname{LH}(p_*P,p_*Q) and vj=(P[p=j],Q[p=j])v_j=(P[p=j],Q[p=j]), so that

L=∑j[0,vj].L=\sum_j[0,v_j].

Fix a size-ss joint test D(x,y)D(x,y). Replacing its first input by the respective proxy changes each acceptance probability by at most ε\varepsilon: fixing yy leaves a size-ss test of xx, and one then averages over yy. For each cell let gj(y)=Ex∼νjD(x,y)g_j(y)=\mathbb{E}_{x\sim\nu_j}D(x,y). Its acceptance pair under PY,QYP_Y,Q_Y belongs to Hs(PY,QY)H_s(P_Y,Q_Y), since it is a convex combination of acceptance pairs of size-ss sections. The proxy joint acceptance pair is

∑jdiag⁡(vj)(EPYgj,EQYgj)∈L⊙Hs(PY,QY).\sum_j\operatorname{diag}(v_j)(\mathbb{E}_{P_Y}g_j,\mathbb{E}_{Q_Y}g_j)\in L\mathbin{\odot}H_s(P_Y,Q_Y).

If computing pp costs TpT_p gates, every Boolean function of pp costs Tp+O(Mlog⁡(M+2))T_p+O(M\log(M+2)) gates by a finite lookup. With this budget denoted by TT, L⊆HT(P,Q)L\subseteq H_T(P,Q), giving

Hs(P⊗PY,Q⊗QY)⊆HT(P,Q)⊙Hs(PY,QY)+Eε.(8)H_s(P\otimes P_Y,Q\otimes Q_Y)\subseteq H_T(P,Q)\mathbin{\odot}H_s(P_Y,Q_Y)+E_\varepsilon. \tag*{(8)}

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 ℓ=log⁡2∣X∣\ell=\log_2|\mathcal{X}| on a full bit-string domain, the corrected bound in that theorem gives

Tp=O(sε−6+ε−12ℓlog⁡(∣X∣/ε)),M=O(ε−1).T_p=O\left(s\varepsilon^{-6}+\varepsilon^{-12}\ell\log(|\mathcal{X}|/\varepsilon)\right),\qquad M=O(\varepsilon^{-1}).

Theorem 1 gives the smaller bound O((s+1)ε−2)O((s+1)\varepsilon^{-2}) 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 Hs(P,Q)⊆L+EεH_s(P,Q)\subseteq L+E_\varepsilon. 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 μ=(P+Q)/2\mu=(P+Q)/2 and g=Q/(P+Q)g=Q/(P+Q), choose the growing test family

G(h)=Cs∪{1{h≥t}:t∈[0,1]},G(h)=\mathcal{C}_s\cup\{\mathbf{1}\{h\ge t\}:t\in[0,1]\},

where Cs\mathcal{C}_s denotes the size-ss Boolean tests. The lemma supplies hh whose residual correlations with every member of G(h)G(h) are at most ε\varepsilon. These are precisely the two conditions used in Lemma 6.

For reciprocal-integer error, their construction uses O(ε−2)O(\varepsilon^{-2}) signed updates with a fixed step of order ε\varepsilon. The running sum can be stored as an integer with O(log⁡(2/ε))O(\log(2/\varepsilon)) bits, and its clipped value has O(1/ε)O(1/\varepsilon) possible outputs. At each step the added test is either a size-ss circuit or a threshold of the existing score. Sharing that score circuit gives total size

O(ε−2(s+log⁡(2/ε))).O\left(\varepsilon^{-2}\left(s+\log(2/\varepsilon)\right)\right).

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 P=PXP=P_X, Q=QXQ=Q_X, μ=(P+Q)/2\mu=(P+Q)/2, and g=Q/(P+Q)g=Q/(P+Q), assigning an arbitrary value where the denominator vanishes. Apply the lemma with the growing family consisting of all size-ss tests, all thresholds of hh, and their complements. For 0<δ≤1/80<\delta\le1/8, the resulting score satisfies

∣Eμf(g−h)∣≤δ\lvert\mathbb{E}_{\mu} f(g-h)\rvert\le\delta

for every such test. The shared-counter implementation described above computes each threshold and its complement with size

T=O(δ−2(s+log⁡(2/δ))).T=O\left(\delta^{-2}(s+\log(2/\delta))\right).

One can take reciprocal-integer δ\delta within a constant factor of any specified tolerance. Since the constant test is included, ∣Eμh−1/2∣≤δ\lvert\mathbb{E}_{\mu}h-1/2\rvert\le\delta. Define probability measures

P~=(1−h)μEμ(1−h),Q~=hμEμh.\widetilde{P}=\frac{(1-h)\mu}{\mathbb{E}_{\mu}(1-h)},\qquad\widetilde{Q}=\frac{h\mu}{\mathbb{E}_{\mu}h}.

For every test in the family, replacing P,QP,Q by these proxies changes each acceptance probability by at most 4δ4\delta: replacing gg by hh costs 2δ2\delta, and normalizing costs at most another 2δ2\delta. The proxy likelihood ratio is monotone in hh. Their statistical hull A=LH⁡(P~,Q~)A=\operatorname{LH}(\widetilde{P},\widetilde{Q}) is therefore the convex hull of the acceptance pairs of score thresholds, their complements, and constants. Consequently

A⊆HT(P,Q)+E4δ.A\subseteq H_T(P,Q)+E_{4\delta}.

Now fix a size-ss joint test D(x,y)D(x,y) and put L=Hs(PY,QY)L=H_s(P_Y,Q_Y). Conditional on any score value of positive μ\mu-mass, the proxies have the common conditional law μ(⋅∣h)\mu(\mathord{\cdot}\mid h) whenever that conditioning event has positive proxy mass. Averaging D(x,y)D(x,y) over this law gives a convex combination of size-ss tests of yy, hence an acceptance pair in LL. Decomposing AA into the segments given by its score masses shows that the proxy joint acceptance pair lies in A⊙LA\mathbin{\odot}L. The original joint pair differs from it by at most 4δ4\delta in each coordinate, since every section D(⋅,y)D(\mathord{\cdot},y) has size at most ss. Lemma 7 now gives

Hs(PX⊗PY,QX⊗QY)⊆HT(PX,QX)⊙Hs(PY,QY)+E8δ.H_s(P_X\otimes P_Y,Q_X\otimes Q_Y)\subseteq H_T(P_X,Q_X)\mathbin{\odot}H_s(P_Y,Q_Y)+E_{8\delta}.

It remains to remove the apparent logarithmic overhead. Take δ\delta of order η/8\eta/8, with 8δ≤η8\delta\le\eta. If s≥log⁡2(1/η)s\ge\log_2(1/\eta), then T=O((s+1)η−2)T=O((s+1)\eta^{-2}) already. Otherwise, fix DD again and discard gates not connected to its output. A fan-in-two circuit with at most ss gates reads at most s+1s+1 distinct input bits, so it reads at most s+1s+1 bits of xx. Let F(x)F(x) record those bits. The section acceptance pair r(x)∈Lr(x)\in L depends only on F(x)F(x). Choose a segment decomposition of r(x)r(x) separately for each value of F(x)F(x). Each coefficient threshold is a Boolean function of at most s+1s+1 bits and has a truth-table circuit of size O((s+1)2s+1)O((s+1)2^{s+1}). Lemma 2 therefore gives exact containment for this joint test with that first-factor budget. Since 2s<1/η2^s<1/\eta, this budget is at most O((s+1)η−2)O((s+1)\eta^{-2}). 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 dX+dY−dXdYd_X+d_Y-d_Xd_Y plus an error decreasing exponentially with a reduction parameter, when dY<1d_Y<1 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

((3/4,1/4),(1/4,3/4))and((1,0),(1/2,1/2))((3/4,1/4),(1/4,3/4)) \quad\text{and}\quad((1,0),(1/2,1/2))

both have total variation distance 1/21/2, but their squares have total variation distances 1/21/2 and 3/43/4, 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 2η2\eta additional distinguishing advantage from an EηE_\eta 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 DD, the sampling proof draws anchors independently from PYP_Y and QYQ_Y. Each coefficient circuit queries the same fixed list of sections D(x,Yi),D(x,Zi)D(x,Y_i),D(x,Z_i) 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 DD one can restrict the small-test family to its sections D(⋅,y)D(\cdot,y): 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 2/δ22/\delta^2, with step size δ/2\delta/2 [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 8δ8\delta, gives 128/η2128/\eta^2 updates at δ=η/8\delta=\eta/8. The number 128128 belongs to this deduction; it is not a bound printed in their paper for a hull theorem.

Two elementary tightenings reduce it. Initializing at h0=1/2h_0=1/2 bounds Eμ(g−h0)2\mathbb{E}_\mu(g-h_0)^2 by 1/41/4. Their prefix-sum proof then gives 1/(2δ2)1/(2\delta^2) updates, without changing the construction. This sharpens the estimate for this initialization, not their statement for an arbitrary prescribed h0h_0. Next, normalization of the proxies is unnecessary: use P^=2(1−h)μ\widehat{P}=2(1-h)\mu and Q^=2hμ\widehat{Q}=2h\mu. Each tested expectation changes by at most 2δ2\delta, and the proxy hull is within E2δE_{2\delta} 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 Eϵ⊙L=EϵE_{\epsilon}\odot L=E_{\epsilon}. The total error is therefore 4δ4\delta. Together these observations give 8/η28/\eta^2 updates.

Projecting after every update, instead of clipping the accumulated sum, gives a further factor of two: with step δ\delta, a violated residual test reduces squared error by more than δ2\delta^2. This gives 1/(4δ2)1/(4\delta^2) updates from initialization 1/21/2, or 4/η24/\eta^2 for error 4δ4\delta. 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 0<η≤10<\eta\le1, the asymmetric containment

Hs(PX⊗PY,QX⊗QY)⊆Hs(PX,QX)⊙Hs(PY,QY)+EηH_s(P_X\otimes P_Y,Q_X\otimes Q_Y)\subseteq H_s(P_X,Q_X)\odot H_s(P_Y,Q_Y)+E_\eta

holds with

S≤⌈η−2⌉s+O(⌈η−2⌉log⁡(2/η)).S\le\lceil\eta^{-2}\rceil s+O\bigl(\lceil\eta^{-2}\rceil\log(2/\eta)\bigr).

More precisely, the construction uses N<κ/η2N<\kappa/\eta^2 updates when κ>0\kappa>0, each containing at most one size-ss circuit, where

κ=12∑x(PX(x)−QX(x))2PX(x)+QX(x)≤1.\kappa=\frac{1}{2}\sum_x\frac{(P_X(x)-Q_X(x))^2}{P_X(x)+Q_X(x)}\le1.

Terms with zero denominator are zero. When κ=0\kappa=0, no updates are needed. The remaining circuit cost is O((N+1)log⁡(2/η))O((N+1)\log(2/\eta)).

Proof. Put P=PXP=P_X, Q=QXQ=Q_X, μ=(P+Q)/2\mu=(P+Q)/2, and g=Q/(P+Q)g=Q/(P+Q) on the support of μ\mu. Set δ=η/2\delta=\eta/2 and initialize h0=1/2h_0=1/2. For each current score hh, consider the growing family

G(h)={f−t: size⁡(f)≤s, t=1{h≥a}, a∈R}.\mathcal{G}(h)=\{f-t:\ \operatorname{size}(f)\le s,\ t=\mathbf{1}\{h\ge a\},\ a\in\mathbb{R}\}.

This includes constant thresholds. Every member has absolute value at most one. If u∈G(h)u\in\mathcal{G}(h) violates ∣Eμ(g−h)u∣≤δ|\mathbb{E}_{\mu}(g-h)u|\le\delta, choose its correlation sign σ\sigma and set

h′=clip⁡[0,1](h+σδu).h'=\operatorname{clip}_{[0,1]}(h+\sigma\delta u).

The potential satisfies

Eμ(g−h′)2≤Eμ(g−h)2−2δ∣Eμ(g−h)u∣+δ2Eμu2<Eμ(g−h)2−δ2.\begin{aligned} \mathbb{E}_{\mu}(g-h')^2\le\mathbb{E}_{\mu}(g-h)^2-2\delta|\mathbb{E}_{\mu}(g-h)u|+\delta^2\mathbb{E}_{\mu}u^2 \\ &<\mathbb{E}_{\mu}(g-h)^2-\delta^2. \end{aligned}

Initially the potential is Eμ(g−1/2)2=κ/4≤1/4\mathbb{E}_{\mu}(g-1/2)^2=\kappa/4\le1/4. Thus the number of updates is strictly less than κ/(4δ2)\kappa/(4\delta^2) if positive, and the final score satisfies

∣Eμ(g−h)(f−t)∣≤δfor all small tests f and thresholds t of h.(9)|\mathbb{E}_{\mu}(g-h)(f-t)|\le\delta\quad\text{for all small tests }f\text{ and thresholds }t\text{ of }h. \tag*{(9)}

The same estimate holds if ff and tt are independently replaced by convex combinations of their respective classes.

Each update evaluates one size-ss 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 η\eta: every score value is of the form b+kδb+k\delta, with b∈{0,1/2,1}b \in\{0,1/2,1\} and an integer ∣k∣=O(1/δ)|k|=O(1/\delta). Store the choice of bb and the integer kk. Clipping resets this representation to an endpoint. Threshold comparisons use hardwired integer cutoffs for each of the three choices of bb. Consequently each update costs at most s+O(log⁡(2/η))s+O(\log(2/\eta)) gates, and a final threshold costs O(log⁡(2/η))O(\log(2/\eta)) gates.

To prove containment, fix a size-ss joint test D(x,y)D(x,y) and set

rP(x)=EPYD(x,Y),rQ(x)=EQYD(x,Y),L=Hs(PY,QY).r_P(x)=\mathbb{E}_{P_Y}D(x,Y), \qquad r_Q(x)=\mathbb{E}_{Q_Y}D(x,Y), \qquad L=H_s(P_Y,Q_Y).

Every (rP(x),rQ(x))(r_P(x),r_Q(x)) lies in LL, and each scalar function rP,rQr_P,r_Q is a convex combination of size-ss tests of xx. Consider a support direction (−a,b)(-a,b) with a,b≥0a,b\ge0, a+b=1a+b=1. Write L=∑j[0,(pj,qj)]L=\sum_j[0,(p_j,q_j)] as above, discarding zero generators. For z∈[0,1]z\in[0,1] choose

tj(z)=1{−a(1−z)pj+bzqj≥0},U(z)=∑jpjtj(z),V(z)=∑jqjtj(z).t_j(z)=\mathbf{1}\{-a(1-z)p_j+bzq_j\ge0\}, \qquad U(z)=\sum_j p_jt_j(z), \qquad V(z)=\sum_j q_jt_j(z).

Each tjt_j is a threshold, or a constant, and (U(z),V(z))(U(z),V(z)) maximizes −a(1−z)u+bzv-a(1-z)u+b zv over (u,v)∈L(u,v)\in L. In particular, at z=h(x)z=h(x),

−a(1−h)(rP−U(h))+bh(rQ−V(h))≤0.-a(1-h)(r_P-U(h))+bh(r_Q-V(h))\le0.

Writing K=HS(P,Q)K=H_S(P,Q), the point

w=(EPU(h),EQV(h))=∑jdiag⁡(pj,qj)(EPtj(h),EQtj(h))w=(\mathbb{E}_P U(h),\mathbb{E}_Q V(h))=\sum_j\operatorname{diag}(p_j,q_j)(\mathbb{E}_P t_j(h),\mathbb{E}_Q t_j(h))

belongs to K⊙LK\odot L, since each threshold of hh has size at most SS. Let zD=(EP⊗PYD,EQ⊗QYD)z_D=(\mathbb{E}_{P\otimes P_Y}D,\mathbb{E}_{Q\otimes Q_Y}D). Subtracting the two support evaluations yields

⟨(−a,b),zD−w⟩=2Eμ[−a(1−g)(rP−U(h))+bg(rQ−V(h))]≤2Eμ(g−h)[a(rP−U(h))+b(rQ−V(h))]≤2δ=η.\begin{aligned} \langle(-a,b),z_D-w\rangle &=2\mathbb{E}_{\mu}\left[-a(1-g)(r_P-U(h))+bg(r_Q-V(h))\right]\\ &\le2\mathbb{E}_{\mu}(g-h)\left[a(r_P-U(h))+b(r_Q-V(h))\right]\\ &\le2\delta=\eta. \end{aligned}

The last step uses (9): U(h)U(h) and V(h)V(h) are convex combinations of score thresholds, with weights summing to one. Taking the supremum over DD proves the support inequality in this quadrant. Both hulls are centrally symmetric about (1/2,1/2)(1/2,1/2), which gives the opposite mixed-sign quadrant. In same-sign directions the support functions agree, since both hulls lie in [0,1]2[0,1]^2 and contain (0,0),(1,1)(0,0),(1,1). Homogeneity now gives the error η∥v∥1\eta\lVert v\rVert_1 in every direction vv, which is precisely containment up to EηE_\eta.

Comparison with sampling. Give a fraction θ∈(0,1)\theta\in(0,1) of the sampling proof’s error budget to polygon approximation. Its explicit cost is

2⌈12(1−θ)η2⌉s+O(1(1−θ)η2+log⁡2(2+((1−θ)η)−2)θη).2\left\lceil\frac{1}{2(1-\theta)\eta^2}\right\rceil s+O\left(\frac{1}{(1-\theta)\eta^2}+\frac{\log^2(2+((1-\theta)\eta)^{-2})}{\theta\eta}\right).

For fixed θ\theta, its coefficient of s/η2s/\eta^2 is (1−θ)−2(1-\theta)^{-2}, approaching one as θ\theta decreases. The optimized regularity proof already has coefficient one (up to integer rounding), but its displayed arithmetic overhead is O(η−2log⁡(2/η))O(\eta^{-2}\log(2/\eta)) rather than Oθ(η−2)O_\theta(\eta^{-2}). 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 4δ4\delta to 2δ2\delta; 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-ss circuit, are

DerivationHull errorUpdate bound at error η\eta
Printed lemma and normalized-proxy deduction8δ8\delta128η−2128\eta^{-2}
Initialization 1/2 and unnormalized proxies4δ4\delta8η−28\eta^{-2}
Projection after every update4δ4\delta4η−24\eta^{-2}
Differences of tests, Proposition 92δ2\deltaη−2\eta^{-2}

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 O((s+1)η−2)O((s+1)\eta^{-2}) bound when the logarithmic arithmetic term would dominate.

References

  1. [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. [2]S. Halevi and T. Rabin. Degradation and Amplification of Computational Hardness. TCC, 2008. https://eprint.iacr.org/2008/102.DOI
  3. [3]N. Geier. A Tight Computational Indistinguishability Bound for Product Distributions. TCC, 2022. https://eprint.iacr.org/2021/1274.DOI
  4. [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. [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. [6]P. Kairouz, S. Oh, and P. Viswanath. The Composition Theorem for Differential Privacy. ICML, 2015. https://proceedings.mlr.press/v37/kairouz15.html.
  7. [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. [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. [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

Paper details

vlnc:W_avhh4895
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents