Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries

arXiv:2609.02880v1 [cs.CR] 2 Sep 2026

Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries Surendra Ghentiyala∗ Cornell University sg974@cornell.edu

Pritish Kamath Google Research pritish@alum.mit.edu

Ravi Kumar Google Research ravi.k53@gmail.com

Pasin Manurangsi Google Research pasin@google.com

September 3, 2026

Abstract We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the ∥ · ∥K -norm mechanism of Hardt and Talwar [HT10]. For the ℓ∞ -error, our algorithm can answer d linear queries with O(d/ε) error using O(log d) random bits, improving upon algorithms of [CSV25, Ghe26]; this is optimal when ε ≤ 1/d. We also provide a computationally efficient version of our algorithm, albeit with an O(log d) multiplicative increase in the error.

∗

Work done during an internship at Google Research.

Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 2

2 Preliminaries 2.1 Convex Geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Differential Privacy (DP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 5

3 Multi-Scale Secluded Partitions 6 3.1 Existence for any ∥ · ∥K -norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 Explicit Construction for the ℓ∞ -norm . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.3 Tail Bounds from MSSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4 Low Randomness Mechanism for any ∥ · ∥K -norm 4.1 Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Randomness Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 14 14 15

5 Efficient Mechanism for ℓ∞ -norm 5.1 Efficiently Enumerating Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Sampling Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Utility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Randomness Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 16 18 20 20 21 21

6 Conclusion and Open Questions

22

1

Introduction

As differential privacy (DP) [DMNS06] has become a gold standard in privacy-preserving algorithms, it has seen large-scale adoption in various real-world systems, both in industry and government sectors. This adoption has revealed several practical challenges in applying DP. One such challenge is randomness complexity—the (expected) number of independent, uniformly random bits required to implement these inherently randomized algorithms. In the US Census deployment of DP, for example, an estimated 7.2 ×1014 random bits were used [GL20]. As such, the randomness complexity has become another important resource constraint—similar to space/time complexity and utility—that can determine the practical applicability of DP algorithms. Motivated by these practical considerations, Canonne et al. [CSV25] initiate the theoretical study of the randomness complexity of DP algorithms. They focus on arguably the simplest and most fundamental problem: Answering d linear queries. In this setting, one can simply apply the classic ε-DP (discrete) Laplace mechanism [DMNS06, GRS12] to achieve an ℓ∞ -error of O(d log d/ε). However, this requires generating independent noise for every one of the d queries, resulting in randomness complexity of at least Ω(d). In a surprising result, Canonne et al. [CSV25] show that the randomness complexity can be significantly reduced. In particular, they give an algorithm1 e 2 /ε). In their that uses only O(log d) random bits in expectation and achieves an ℓ∞ -error of O(d algorithm, it is also possible to trade off more randomness complexity with lower error. Nevertheless, at the other extreme of O(d log d/ε) error, matching the Laplace mechanism, their algorithm’s randomness complexity remains Ω(d), similar to the Laplace mechanism. A subsequent work of Ghentiyala [Ghe26] simplified and improved the efficiency of their algorithm. More recently, Kalinin and Pagh [KP26] explored the randomness complexity (and practical efficiency) of variants of the Gaussian and Laplace mechanism in a model that allows access to both public and private randomness. Still, the overall randomness complexity vs utility tradeoff has remained unchanged from [CSV25] up to logarithmic factors. This brings us to the central question we study: What is the inherent tradeoff between the randomness complexity and utility for answering DP linear queries?

1.1

Our Results

Surprisingly, we show that there is no tradeoff at all: We can achieve both (nearly) optimal utility and randomness complexity simultaneously, as stated below. Theorem 1.1 (Informal; See Corollary 4.2). There is an ε-DP mechanism that can answer d linear queries with expected ℓ∞ -error O(d/ε) and randomness complexity O(log d). As we show later, the above theorem also holds for a broad family of norms, but for the discussion below, we focus on the ℓ∞ -norm. Note that in the ℓ∞ -norm, the error bound is even better than the standard Laplace mechanism [DMNS06, GRS12] by an O(log d) factor and is in fact optimal [HT10, SU16]. As for the randomness complexity, [CSV25] prove that Ω(log d) is necessary in the high-privacy regime where ε ≤ 1/d. It remains an interesting open question to extend this lower bound to larger ε. 1 They also provide an algorithm that satisfies approximate-DP. Nevertheless, our pure-DP algorithm already improves on it in the low-randomness-complexity regime. See § 6 for a more detailed discussion.

1

Though the above mechanism is not efficient, it demonstrates that O(log d) bits of randomness (in expectation) is sufficient to answer linear queries with optimal expected error. Nevertheless, we also give a polynomial time mechanism for this task, but with an error bound that is an O(log d) factor larger than the above bound (hence matching that of the Laplace mechanism). Theorem 1.2 (Informal; See Theorem 5.1). Let ε < log d. There is an efficient ε-DP mechanism that can answer d linear queries with expected ℓ∞ -error O((d log d)/ε) and randomness complexity O(log d).

1.2

Technical Overview

For a dataset X ∈ X ∗ , let f : X ∗ → Rd denote the function of interest. Throughout this overview, we assume that its ℓ∞ -sensitivity is bounded by one. In the case of linear queries, we adhere to P the standard DP convention that f (x) = ϕi (xi ) where ϕi has co-domain [0, 1]. Therefore, the assumption that f has ℓ∞ -sensitivity bounded by one generalizes the d linear queries setting, as we can view f (X)i as the answer to the ith linear query. Secluded Partition. To describe our algorithm and that of [CSV25], we recall the crucial notion of secluded partition and its construction from2 Woude et al. [WDP+ 22, WDP+ 23]. Definition 1.3 (Secluded Partition). For ρ > 0, a partition P of Rd is called a (k, γ; ρ)-secluded partition with respect to the norm ∥ · ∥ if there exists a function r : P → Rd such that r(P ) ∈ P for all P ∈ P such that the following hold: • For all P ∈ P and for all x ∈ P , it holds that ∥r(P ) − x∥ ≤ ρ. • Any ∥ · ∥ ball of radius γ · ρ intersects at most k cells in P. Sometimes, we omit the parameter ρ to mean that it is a (k, γ; ρ) secluded partition for some ρ.3 We refer to r(P ) as the representative of P , and the map R : x 7→ r(P ) where x ∈ P ∈ P as the rounding function. Given a secluded partition P, the algorithm in [CSV25] can be loosely described as follows: • Add Laplace noise to f (X) to obtain Y . • Find the partition cell P ∈ P to which Y belongs. • Output the representative r(P ) of cell P . The scale parameter ρ is selected so that the Laplace noise added is of norm at most γ · ρ with high probability. The crux of the analysis from [CSV25] is that, due to the second property of the secluded partition, with high probability the output of the mechanism will be one of these k partition cells. Via a slightly more careful analysis, one can show that this implies that the entropy of the output is also O(log k). A standard argument by Knuth and Yao [KY76] then implies that this distribution can be sampled using O(log k) independent bits of randomness (in expectation). In terms of the high-probability error bound, since the norm of the Laplace noise is at most γ · ρ and rounding to the representative adds an error of at most ρ, the triangle inequality ensures that the error is O(ρ). 2 3

See also [WDP+ 24], which is a conference version of these works. Note that a (k, γ; ρ)-secluded partition can be scaled to obtain a (k, γ; ρ′ )-secluded partition for all ρ′ > 0.

2

Our Algorithm. Instead of a two-stage analysis of Laplace noise and rounding, our main idea is to forego the noise, and simply use the exponential mechanism [MT07] on the representatives of the secluded partition, using a score of the distance of f (X) from the corresponding cells. More formally, let the distance from a point z ∈ Rd to a partition cell P ∈ P be defined as ∆P (z) := inf y∈P ∥z −y∥∞ (we only consider ∥ · ∥∞ in this overview, though our mechanism works for a large class of norms; see § 3.1). Crucially, we define the distance to a cell P to be the minimum distance to any point in P rather than the distance to the representative of P ; this will prove important in our analysis. It is easy to see that the sensitivity of ∆P (f (·)) is bounded by the sensitivity of f (in the given norm). As such, the exponential mechanism is ε-DP as desired. Thus, most of our technical contribution is in analyzing the randomness complexity of this mechanism. Randomness Complexity. Once again, our proof of the randomness complexity essentially boils down to showing that when the scaling factor ρ of a secluded partition is selected appropriately, the output is, with high probability, from a small number of partitions. To explain the proof and parameter selection in more detail, we need to be more specific about the parameters of secluded partitions. First, let us recall the construction from [WDP+ 22, WDP+ 23]4 : Theorem 1.4 ([WDP+ 23]). For every ℓ ∈ [d], there is an ((ℓ + 1)O(d/ℓ) , 1/2ℓ)-secluded-partition. Crucially however, the choice of the partition in the above construction depends on the value of ℓ. Our first contribution is to show that there is, in fact, a single partition that is simultaneously secluded with similar parameters for all ℓ. We refer to this as a multi-scale secluded-partition. Definition 1.5 (Multi-Scale Secluded Partition). Let ρ ∈ R>0 , d ∈ Z>0 and kd : [d] → Z>0 be a function. P is a (kd , ρ)-multi-scale secluded partition ((kd , ρ)-MSSP) with respect to the norm ∥ · ∥ if for all ℓ ∈ [d], P is a (kd (ℓ), 1/ℓ; ρ)-secluded partition with respect to the norm ∥ · ∥. We omit ρ in (kd , ρ)-MSSP to mean “for some ρ” (again, one can modify the ρ easily via scaling). We use the probabilistic method to prove the existence of such a MSSP. Theorem 1.6 (Informal; See Theorem 3.2). For any d ∈ N, there is a kd -MSSP for the ℓ∞ -norm, where kd (ℓ) = dO(1) · 2O(d/ℓ) . We note that, interestingly, the parameters we obtain in the above theorem are better than those of the (single-scale) secluded-partition from [WDP+ 23] in certain regimes, e.g., Θ(1) ≤ ℓ ≤ Θ(d/ log d); see Theorem 1.4. This might be of independent interest. Proof Overview. We are now ready to discuss the core argument in the proof. We set ρ = Θ(d/ε) where “Θ” contains a sufficiently large constant. Then, we claim that the algorithm will, with high d probability, output only a partition cell that is within distance ρ log of f (X). Note that this implies d ρ log d that the error is at most ρ + d = O(d/ε). Moreover, since there are only dO(1) such partition cells, it is not hard to further show that the entropy of the output is at most O(log d), which yields the desired randomness complexity. The high-level intuition for the claim is as follows. First, it is not hard to show that faraway partition cells, i.e., those with ∆P (f (X)) > ρ, are selected with very low total probability. Among the remaining partition cells, we can group them into “rings” based on distances; namely, for each 4

Note that the bounds in [WDP+ 22, WDP+ 23] are more refined. However, since we are only interested in asymptotic results, we consider this simplified version.

3

ℓ ∈ [d/ log d], we can consider the group of all cells P where ∆P (f (X)) ∈

h

ρ ρ ℓ+1 , ℓ



. Since P is an

MSSP, by Theorem 1.6, there are at most dO(1) 2O(d/ℓ) ≤ exp(O(d/ℓ)) such cells. However, the  ρ ε exponential mechanism assigns probability at most exp − 2 · ℓ+1 = exp(−Θ(d/ℓ)) to each such cell. Thus, by picking the constant in big-Θ to be sufficiently large, the probability of selecting any such cell is small. Finally, a union bound over all these rings concludes the proof. Extensions to Other K-Norms. Finally, as an astute reader might have already noticed, our mechanism does not use any specific property of the ℓ∞ -norm, apart from the existence of a multi-scale secluded-partition. It turns out that, via a simple probabilistic argument, a multi-scale secluded-partition exists very generally across a large class of K-norms for “somewhat nice” K. As a result, it is simple to extend our mechanism to match the error of the so-called K-norm mechanism by Hardt and Talwar [HT10], where K is the sensitivity polytope (Definition 2.6) of the function f . In particular, for ℓp -norms, we can still get an ℓp -error of O(d/ε) using O(log d) bits of randomness. Computationally Efficient Mechanism. The probabilistic construction of an MSSP does not immediately yield an efficient mechanism. However, for the special case of the ℓ∞ -norm, we construct an explicit MSSP, and show that the algorithm using it can be implemented efficiently. The MSSP, however, has slightly worse parameters, leading to an error of O((d log d)/ε) with randomness complexity of O(log d). The MSSP itself can be viewed as a modification of the partition by Hoza and Klivans [HK18]. The parameters we obtain for this MSSP essentially match those of [WDP+ 22, WDP+ 23] (Theorem 1.4), which are worse than the probabilistic construction. This results in the O(log d) factor increase in the error. Closing this gap is an interesting open problem.

2

Preliminaries

2.1

Convex Geometry

Let Bpd (r) denote the ℓp -ball of radius r in Rd . For any absorbing disk5 K that does not contain a nontrivial subspace of Rd , define the ∥ · ∥K -norm as ∥z∥K := inf{t ≥ 0 : z ∈ tK}.

(1)

Throughout this work, we assume that K is an absorbing disk not containing a nontrivial subspace of Rd and hence satisfies the conditions needed to make ∥ · ∥K a norm. Note that the notion of ∥ · ∥K -norm subsumes all ℓp -norms. Definition 2.1 (δ-net). For a set K ⊂ Rd and norm ∥ · ∥ on Rd , we say that a finite set A ⊆ K is a δ-net for K with respect to ∥ · ∥ if for all x ∈ K, there exists y ∈ A such that ∥x − y∥ ≤ δ. Lemma 2.2 ([Pis99, Lemma 4.16 rephrased]). Let ∥ · ∥1 , ∥ · ∥2 be two arbitrary norms on Rd with respective unit balls B1 , B2 where B2 ⊆ B1 . Let δ > 0. There is a finite set A ⊂ B1 that is a δ-net for B1 with respect to ∥ · ∥2 with 2 |A| ≤ 1 + δ 

d

·

vol(B1 ) . vol(B2 )

A set K ⊆ Rd is an absorbing disk if (i) it is convex, (ii) it is symmetric, i.e., K = −K, and (iii) for all z ∈ Rd , there exists t ∈ R≥0 such that z ∈ tK. 5

4

Theorem 2.3 (John’s Theorem [Joh48]; [TV06, Theorem 3.13 rephrased]). Let K be a symmetric convex body in Rd (namely K = −K). Then there exists an invertible linear transformation T : Rd → Rd such that √ where T K := {T z | z ∈ K}. B2d (1) ⊆ T K ⊆ B2d ( d),

2.2

Differential Privacy (DP)

We recall the definition of (pure-) DP [DMNS06] below. The definition relies on a symmetric notion of neighboring datasets, denoted X ∼ X ′ ; some typical neighborhood notions are adding/removing one element, or replacing one element to obtain dataset X ′ from X (or vice versa). A mechanism M : X ∗ → ∆O maps datasets X ∈ X ∗ to probability measures over the output space O. Definition 2.4 (Differential Privacy). A mechanism M : X ∗ → ∆O is ε-differentially private (ε-DP) if, for any pair X ∼ X ′ of neighboring datasets and any measurable set E ⊆ O, it holds that Pr[M(X) ∈ E] ≤ eε · Pr[M(X ′ ) ∈ E]. When O is countable, this is equivalent to requiring that, for all o ∈ O, Pr[M(X) = o] ≤ eε · Pr[M(X ′ ) = o]. For the purposes of our results, the exact neighborhood notion is irrelevant, as long as the function f has low sensitivity for neighboring datasets. Definition 2.5 (Sensitivity). Let f : X ∗ → Rd be a function, and ∥ · ∥ be any norm over Rd . The sensitivity of f with respect to ∥ · ∥ is defined as sens∥·∥ (f ) = supX∼X ′ ∥f (X) − f (X ′ )∥. For the special case of d = 1, we assume throughout that the norm is the absolute value and will henceforth omit it from the notation. It is also useful to define the notion of a sensitivity polytope, as follows. Definition 2.6 (Sensitivity Polytope). We say that K ⊆ Rd is a sensitivity polytope of f if f (X) − f (X ′ ) ∈ K for all neighboring datasets X ∼ X ′ . Note that in the above definition, a sensitivity polytope for f might not be unique. This is somewhat more convenient for our exposition below (instead of defining the sensitivity polytope to be the unique smallest such polytope). The sensitivity of f and the sensitive polytope of f relate to each other as follows: Observation 1. Let K be a sensitivity polytope of f . Then, we have sens∥·∥K (f ) ≤ 1. Proof. For any neighboring X ∼ X ′ , we have f (X) − f (X ′ ) ∈ K. Using the definition of ∥ · ∥K -norm (see (1)), it follows that ∥f (X) − f (X ′ )∥K ≤ 1. The exponential mechanism [MT07] is parameterized by the output set O and a scoring function {scro }o∈O , where scro : X ∗ → R. The algorithm simply outputs each o ∈ O with probability
ε proportional to exp − 2 · scro (X) . The privacy guarantee of the mechanism is given below: Theorem 2.7 (Exponential Mechanism, [MT07]). If scro has sensitivity at most 1 for all o ∈ O, then the exponential mechanism is ε-DP. Adopting the conventions of [CSV25], we now define the output entropy and randomness complexity of a mechanism. 5

Definition 2.8 (Output Entropy). The output entropy of a mechanism M : X ∗ → ∆O is defined as supX∈X ∗ H(M(X)), where H(·) is the Shannon entropy. Definition 2.9 (Randomness Complexity). The randomness complexity of a mechanism M : X ∗ → ∆O is defined as the supremum over X ∈ X ∗ of the expected number of random bits used by M(X). Output entropy is a purely information-theoretic notion while randomness complexity is also a computational notion. We have intentionally left out the model of computation in Definition 2.9. When we design our efficient mechanism in §5, we will work with the standard notion of a probabilistic Turing machine running in polynomial time. However, in all other instances, we will assume that the model of computation for which we are measuring randomness complexity is as general as possible (e.g., an infinite decision tree reading the input and some number of random bits). This will allow us to use the DDG-tree sampler of Knuth and Yao [KY76] to smoothly transition between output entropy and randomness complexity. Theorem 2.10 (paraphrased [KY76]). Let p = (p1 , . . . , pn ) be a discrete probability distribution (where n may be infinite). The average number of random bits used by an optimum DDG-tree algorithm for p is at most H(p) + 2 where H(·) denotes the binary entropy function. For the algorithm described in § 5, it is essential to provide an efficient method for sampling from the distribution rather than merely establishing a bound on the entropy. For this, we will need to generate a Ber(p) random variable as a subroutine. This can be done efficiently and with low randomness, since it is a special case of the Knuth–Yao sampler [KY76] where the DDG-tree construction and execution are polynomial time (a formal proof of a more general version of Lemma 2.11 can be found in the appendix of [Ghe26]). Lemma 2.11. For a t-bit value p, we can sample from Ber(p) in poly(t) time and using O(1) bits of randomness in expectation.

3

Multi-Scale Secluded Partitions

In this section, we will consider multi-scale secluded partitions (MSSPs) solely as a geometric object and show their existence, an explicit construction, and useful properties. We recall the definition. Definition 1.5 (Multi-Scale Secluded Partition). Let ρ ∈ R>0 , d ∈ Z>0 and kd : [d] → Z>0 be a function. P is a (kd , ρ)-multi-scale secluded partition ((kd , ρ)-MSSP) with respect to the norm ∥ · ∥ if for all ℓ ∈ [d], P is a (kd (ℓ), 1/ℓ; ρ)-secluded partition with respect to the norm ∥ · ∥. MSSPs generalize secluded partitions (see Definition 1.3 and Theorem 1.4) by demanding a stronger order of quantifiers. Rather than asking that for every ℓ, there exist a (kd (ℓ), 1/ℓ; ρ)-secluded partition Pℓ , we require a single P that is a (kd (ℓ), 1/ℓ; ρ)-secluded partition for all ℓ ∈ [d].

3.1

Existence for any ∥ · ∥K -norm

We will first show that for K that are sandwiched between inner and outer ℓ2 -balls of appropriate sizes, there exists an MSSP for the ∥ · ∥K norm. We will then generalize this to any K by applying the proper transformation.

6

√ Lemma 3.1. Let K ⊂ Rd be any set such that ∥ · ∥K is a norm and B2d (1) ⊆ K ⊆ B2d ( d). There exists a kd -MSSP for ∥ · ∥K , where kd (ℓ) = O(d log d · ed/ℓ ). √ Proof. Let T = Rd /(LZd ) be the flat torus with side length L = 20 d. Let the distance in the torus be given by dT (x, y) := minz∈LZd ∥x − y + z∥K . Let η = 1/(4d). We construct an η-net Nη on the torus T, in which the elements of the net will be our anchor points. In fact, it suffices to construct the η-net on [−L/2, L/2]d since distances on the flat torus cannot be any greater than on [−L/2, L/2]d . By Lemma 2.2, d 2 vol([−L/2, L/2]d ) |Nη | ≤ 1 + · 1/(4d) vol(K) vol([−L/2, L/2]d ) ≤ (9d)d · vol(B2d (1)) √ ≤ (9d)d (20 d)d (d!)





= 2O(d log d) . Let λ = C · d log(d + 1) for a sufficiently large constant C. We choose 

s= λ·

vol(T) , vol(K) 

independent points uniformly from T to create a subset S. Our secluded partition will correspond to the Voronoi cells of each point in S with respect to dT (·, ·). Formally, the partition is defined as PS := {Pw | w ∈ S} where Pw := {x ∈ Rd | w = argminw′ ∈S dT (x, w′ )}, and the representative function is r(Pw ) := w for all w ∈ S. We now show that both the covering and secludedness properties hold with high probability. Covering. We first show that with high probability, every point x ∈ T is within distance 1 of some point in S. To do so, we will show that with high probability each anchor point is within distance 1 − η of some point in S. Note that this is sufficient as it would imply that for any x ∈ T, x is within distance η of an anchor point, which is itself within distance 1 − η of S, so x is within distance 1 of S by the triangle inequality. For q ∈ Nη , let Eq denote the event that no element in S lands within distance 1 − η of q and E denote the union of events Eq over q ∈ Nη . Now, vol((1 − η)K) Pr[Eq ] = 1 − vol(T) 

s

d vol(K)



≤ 1 − (1 − η)

vol(T)

λ vol(T)

vol(K)

d

≤ e−λ(1−η) ≤ e−λ/100 .

We can then union bound over Nη to conclude that E occurs with small probability. Indeed, Pr[E] ≤

X

Pr[Eq ] ≤ |Nη | · e−λ/100 ≤ 2O(d log d) · e−λ/100 ≤ 0.01,

q∈Nη

for a sufficiently large constant C. From now on, we assume that the covering property holds.

7

Secludedness. Suppose the secludedness condition is violated for some fixed ℓ, i.e., there exists a point x ∈ T such that the ball of radius 1/ℓ around x intersects more than 6C · d log(d + 1) · ed/ℓ cells. By the covering property, this implies that the ball of radius 1 + 1/ℓ around x intersects more than 6C · d log(d + 1) · ed/ℓ points in S. Furthermore, since x is within distance η of some point q in Nη , we have that the ball of radius rℓ := 1 + 1/ℓ + η around q intersects more than 6C · d log(d + 1) · ed/ℓ points in S. It is therefore sufficient to upper bound the probability that there exists q ∈ Nη such that Fq := |S ∩ (q + rℓ K)| > 6C · d log(d + 1) · ed/ℓ . Let Eℓ,q be the event this happens. Note that Fq is the sum of s i.i.d. Bernoulli random variables: E[Fq ] = s

vol(rℓ K) rd · vol(K) =s ℓ = rℓd · λ. vol(T) vol(T)

Next, we bound rℓd . Clearly rℓd ≥ 1, while 

rℓd = 1 +

1 +η ℓ

d



= 1+

1 1 + ℓ 4d

d

1 1 ≤ e( ℓ + 4d )·d ≤ 2ed/ℓ .

Using a simple Chernoff bound, d

Pr[Eℓ,q ] = Pr[Fq > 6C · d log(d + 1) · ed/ℓ )] ≤ Pr[Fq > 3λ · rℓd ] ≤ 2−λ·rℓ ≤ 2−λ , where we used 6C · d log(d + 1) · ed/ℓ ≥ 3λrℓd . We can then union bound over Nη to conclude that E = ∪ℓ,q Eℓ,q occurs with small probability. Indeed, Pr[E] ≤

X X

Pr[Eℓ,q ] ≤ d · |Nη | · 2−λ = d · 2O(d log d) · 2−C·d log(d+1) ≤ 0.01.

ℓ∈[d] q∈Nη

By the probabilistic method, a covering and secluded set S of size s exists for T. We can now create such a set S for all of Rd simply by letting S = S + LZd . Since S + K = T, S + K = Rd . Thus, every point in Rd is within ∥ · ∥K distance 1 of some point in S. The Voronoi cells of each point in S with respect to ∥ · ∥K -norm yields the MSSP partition P (with scaling factor ρ = 1). Theorem 3.2. Let K ⊂ Rd be any symmetric set such that ∥ · ∥K is a norm. There exists a kd -MSSP for ∥ · ∥K , where kd (ℓ) = O(d log d · ed/ℓ ). Proof. By John’s theorem (Theorem 2.3), there exists an invertible linear transformation T : Rd → √ d d d f f R such that if we let K = T (K), then B2 (1) ⊆ K ⊆ B2 ( d). Observe that z ∈ tK if and only if T (z) ∈ T (tK) = t · T (K). Therefore, ∥x∥K = ∥T (x)∥K e , so T preserves distances. d/ℓ e By Lemma 3.1, there is a kd -MSSP P for ∥ · ∥K e , where kd (ℓ) = O(d log d · e ). e with the representative function r(T −1 (Pe )) = Define a partition of Rd by P = {T −1 (Pe ) | Pe ∈ P} −1 e T re(P ). We now show that P has the two desired properties. First, if P = T −1 (Pe ) ∈ P and x ∈ P , then T x ∈ Pe , hence ∥x − r(P )∥K = ∥T (x) − T (r(P ))∥K e ≤ 1. Next, we show the secludedness property. Consider any point v ∈ Rd and let us consider all the partition cells of P intersected by v + (1/ℓ)K, in other words, those within distance 1/ℓ of v in the ∥ · ∥K norm. It suffices to upper bound 1 {P ∈ P : P ∩ v + K ℓ 



1 ̸= ∅} = {P ∈ P : T (P ) ∩ T v + K ̸= ∅} ℓ   1 f ̸= ∅} ≤ O(d log d · ed/ℓ ). = {Pe ∈ Pe : Pe ∩ T (v) + K ℓ 

8



We remark that our construction of an MSSP for ∥ · ∥K is essentially the same as that of random coverings studied by Rogers [Rog57], who considered the question of how to cover Rd using K with minimum density. Our construction can be viewed as placing a copy of K, centered at all points in S. The fact that S + K = Rd ensures that this is a covering of the space. However, our objective is different. A more related objective comes from the follow up work of Erdős and Rogers [ER62], who aimed to bound the multiplicity (i.e., number of times it is covered) of any point in Rd . This is similar to our objective when the threshold distance γ · ρ approaches zero. However, it still does not account for the case of general (and multiple) values of γ. Thus, we are not aware of any method that recovers an MSSP directly from prior work.

3.2

Explicit Construction for the ℓ∞ -norm

In this section, we give an explicit construction of a rounding scheme that implicitly defines an MSSP induced by the pre-image of the rounding scheme. Though this scheme has slightly worse parameters than those of § 3.1, it has the advantage of being explicit and has an efficient rounding function. Indeed, the rounding function can be implemented in polynomial time, and this will be key to our construction of a polynomial time, low randomness mechanism later in § 5. 3.2.1

Rounding Scheme and Properties

We first define a rounding scheme R (Algorithm 1), which rounds points in Rd to a representative point. We can then define the partition induced by R by partitioning all x ∈ Rd according to the points to which they would round under R. See Figure 1 for a visualization of the partition induced by Algorithm 1 for d = 2. We use {y} = y − ⌊y⌋ to denote the fractional part of y. y 2

)

x3

1

x2

R

(x

2)

R(x 3

0

−1

R(

x1

)

−2

1

2

x

x1

−1

−2

Figure 1: The induced two-dimensional ℓ∞ -MSSP from Algorithm 1. Included are example points x1 , x2 , x3 along with where they would be rounded under R.

9

Algorithm 1 ℓ∞ Rounding Scheme R Parameters: d ∈ Z>0 Input: Point x ∈ Rd For each a ∈ {0, . . . , d − 1}, compute Φa (x) = A(x) ← argmina Φa (x) for i ∈ [d] do j k A(x) yi ← A(x) + x − i d d

Pd

a i=1 {xi − d }

▷ break ties by choosing smallest such a

return (y1 , . . . , yd ) We first show that the ℓ∞ -error due to rounding is small. Lemma 3.3. For all d ∈ Z>0 and x ∈ Rd , ∥R(x) − x∥∞ ≤ 1. Proof. We will show that for each i ∈ [d], |yi − xi | ≤ 1. Note that for all 0 ≤ z < 1, xi − 1 ≤ ⌊xi − z⌋ + z ≤ xi . Setting z = A(x)/d confirms |yi − xi | ≤ 1. We now prove the key properties underlying the fact that R induces a good MSSP: that if A(x) = a, then not many coordinates i can have {xi − a/d} close to 1. For the remainder of this section, we fix d ∈ Z>0 , x ∈ Rd and use the notation from Algorithm 1. Lemma 3.4. For all a, b ∈ {0, . . . , d − 1}, if b ≡ a − m (mod d) for some m ∈ {0, . . . , d − 1}, then 

Φb (x) − Φa (x) = m −

a i : xi − d 



m ≥1− d



.

Proof. Let ti = xi − ad ∈ [0, 1). By periodicity, 

b m m − 1ti ≥1−m/d , = ti + = ti + d d d where 1 denotes the indicator function. Now, the change in Φ is exactly 







xi −

Φb (x) − Φa (x) = =

d  X i=1 d  X i=1

b xi − d



a − xi − d 

m − 1ti ≥1− md d





=

d  X i=1

=m−



m ti + d

m i : ti ≥ 1 − d





− ti



.

Lemma 3.5. For every θ ∈ [0, 1], 



i ∈ [d] : xi −

A(x) d



≥1−θ



≤ dθ + 1.

Proof. Let a = A(x) and let ti = xi − ad ∈ [0, 1). Consider any b, m ∈ [0, d−1] such that b ≡ a−m (mod d). Since a minimizes Φa (x), we have Φb (x) − Φa (x) ≥ 0. By Lemma 3.4, 



m−

m i : ti ≥ 1 − d



= Φb (x) − Φa (x) ≥ 0.

This yields i : ti ≥ 1 − m ≤ m. For any θ ∈ [0, 1], choose m = ⌈dθ⌉. Note that if m = d, the d lemma is trivially true since this would imply dθ + 1 ≥ d. Therefore, we assume m ∈ [0, d − 1]. m Since m d ≥ θ, any coordinate i with ti ≥ 1 − θ also satisfies ti ≥ 1 − d . Thus, the number of such coordinates is at most m = ⌈dθ⌉ ≤ dθ + 1. 

10

3.2.2

Bounding Intersected Partition Cells

We now prove that any sufficiently small ball only intersects relatively few partition cells of the partition induced by R, satisfying the second condition of an MSSP. In this section, let B∞ (x; r) denote the ℓ∞ -ball of radius r centered at x. Lemma 3.6. Fix d ∈ Z>0 , x ∈ Rd , and define R as in Algorithm 1. For every ℓ ∈ [d], |R(B∞ (x; 1/ℓ))| ≤ (ℓ + 1)O(d/ℓ) . Proof. Let r = 1/ℓ. For any fixed shift a ∈ [0, d − 1] for any point z ∈ B∞ (x; r), the shifted values zi − a/d lie in an interval of length 2r = 2/ℓ. We handle two cases based on this length. (i) Small ℓ: ℓ ≤ 2. Since the interval length is 2/ℓ ≤ 2, for any fixed a, there are at most three possible values for ad + ⌊zi − ad ⌋ over z ∈ B∞ (x; r). So across the d possible shifts a, the total number of vectors in R(B∞ (x; 1/ℓ)) is at most d · 3d . Because ℓ ≤ 2, we have d ≤ 2(d/ℓ), so d · 3d ≤ 2O(d/ℓ) ≤ (ℓ + 1)O(d/ℓ) . (ii) Large ℓ: ℓ ≥ 3. Here, the interval length 2r = 2/ℓ < 1. Therefore, for each fixed shift a, over z ∈ B∞ (x; r), after rounding, each coordinate takes at most two adjacent values for ad + ⌊zi − ad ⌋. Let Mi (a) = maxy∈B∞ (x;r) ⌊yi − a/d⌋. Consider a point z ∈ B∞ (x; r) that selects shift A(z) = a. Say ⌊zi − a/d⌋ does not take the maximum floor value Mi (a). Then, we must have ⌊zi − a/d⌋ = Mi (a) − 1. Furthermore, by the definition of Mi (a), ⌊xi + 1/ℓ − a/d⌋ = Mi (a), which implies xi + 1/ℓ − a/d ≥ Mi (a). Since zi + 1/ℓ ≥ xi , we have zi + 2/ℓ − a/d ≥ Mi (a). Rearranging leaves us with zi − a/d ≥ Mi (a) − 2/ℓ. This, together with the fact that ⌊zi − a/d⌋ = Mi (a) − 1, implies that the fractional part of zi − a/d is tightly bounded:     a a 2 zi − = zi − − (Mi (a) − 1) ≥ 1 − . d d ℓ So we have established that if ⌊zi − a/d⌋ = Mi (a) − 1, then {zi − a/d} ≥ 1 − 2/ℓ. So by Lemma 3.5 with θ = 2/ℓ, for any z ∈ B∞ (x; r), there exist at most k = ⌊2d/ℓ⌋ + 1 coordinates i ∈ [d] such that ⌊zi − a/d⌋ = Mi (a) − 1. Thus, R(z) is completely determined by a and this subset of at most k coordinates. Since 3 ≤ ℓ ≤ d, we have k ≤ 2d/ℓ + d/ℓ = 3d/ℓ ≤ d. Summing over all d shifts and using the standard binomial tail bound most |R(B∞ (x; r))| ≤ d

d
j=0 j ≤

Pk

! k X d j=0

j



ed k

3d/ℓ

≤d

X j=0

k

, the number of values R(z) takes on over z ∈ B∞ (x; r) is at !

d j

ed ≤d 3d/ℓ 

3d/ℓ

eℓ =d 3 

3d/ℓ

≤ dℓ100d/ℓ = (ℓ + 1)O(d/ℓ) .

By combining Lemma 3.3 and Lemma 3.6, we conclude: Theorem 3.7. For any d ∈ Z>0 , the partition induced by Algorithm 1 is a kd -MSSP for kd (ℓ) = (ℓ + 1)O(d/ℓ) .

3.3

Tail Bounds from MSSPs

Our definition of an MSSP with scaling factor ρ only tells us how many partition cells can intersect a ball of discrete radius ρ/ℓ for ℓ ∈ [d]. It does not bound the number of partition cells a ball of real-valued radius more than ρ/d may intersect. Although the definition of an MSSP does not bound this quantity, we can bound it by using the properties of an MSSP. 11

Recall that ∆P (x) := inf z∈P ∥x − z∥. For a fixed y ∈ Rd , let P<γ (y) = {P ∈ P | ∆P (y) < γ · ρ}. The case γ ∈ [1/d, 1] is easy. Lemma 3.8. Let P be a kd -MSSP for kd (ℓ) = m(d) · eλ(d)/ℓ , where m(·) and λ(·) are functions. For any y ∈ Rd and for any γ ∈ [1/d, 1], |P<γ (y)| ≤ m(d) · e2λ(d)·γ . Proof. Since γ ≤ 1, we have 1/(2γ) ≤ ⌊1/γ⌋ := ℓ. Furthermore, 1/ℓ ≥ γ. For any y, λ(d)

|P<γ (y)| ≤ |P<1/ℓ (y)| ≤ m(d) · e ℓ

≤ m(d) · e2λ(d)·γ .

Next we address the case γ > 1. Lemma 3.9. If P is a kd -MSSP with respect to ∥ · ∥K , then for any y ∈ Rd and γ ≥ 1, |P<γ (y)| ≤ kd (1) · (3γ)d . Proof. Assume without loss of generality that y = 0. We may also rescale the grid to ρ = 1 without affecting |P<γ (y)|, so assume ρ = 1. Let δ = 1, B1 = γK, and B2 = K. By Lemma 2.2, γK can be covered by a δ-net of size at most 3d γ d . Now place a ∥ · ∥K ball of radius ρ around each δ-net point. Furthermore, the MSSP bound guarantees that each ball of radius ρ intersects at most kd (1) cells. Summing over all of the points in the δ-net, γK intersects at most kd (1) · 3d γ d partition cells. We now show the useful property of good MSSPs with proper scaling ρ: if a partition cell P is sampled with probability proportional to exp(− 2ε sP (v)) for any upper bound sP (v) ≥ ∆P (v), then the probability that P is at a distance greater than γ from v decays exponentially with γ. Lemma 3.10. Let ε > 0, α ≥ 1, M ≥ 1, A > 0. Let A′ = max(2A, A + 3) and C = 2A′ + 2. Let Aαd/ℓ . Let v ∈ Rd be arbitrary and s (·) be a P be a (kd , ρ)-MSSP for ρ = Cαd P ε where kd (ℓ) ≤ M e nonnegative function such that sP (v) ≥ ∆P (v) for all P ∈ P and sP0 (v) = 0 for some P0 . Consider sampling P ∈ P with probability proportional to exp(− 2ε sP (v)). Then, Pr[P ∈ / P<γ ] ≤ 2M · e(2A+1)α−αdγ , for γ ≥ 1/d. Proof. Let k = ⌊γd⌋ ≥ 1. We bound the tail probability by summing over rings of step size 1/d: Pr[P ∈ / P<γ ] ≤

∞ X j=k

h

Pr P ∈ P< j+1 \ P< j d

i

d

∞ X

∞ X ε j Cα ≤ |P< j+1 | · exp − · ρ = |P< j+1 | · exp − j , d d 2 d 2 j=k j=k









where the second inequality follows by observing that, for any ring j, the probability of sampling P is at most exp(− 2ε sP (v)) (since sP0 (v) = 0 causes the normalizing factor to be at least 1), which is at most exp(− 2ε ∆P (v)) since sP (v) ≥ ∆P (v), and ∆P (v) ≥ dj ρ by assumption. The final equality follows from our choice of ρ. Let A and B be universal constants such that kd (ℓ) ≤ M eAαd/ℓ . We bound |P< j+1 | in two cases: d

j+1

(i) j < d. By Lemma 3.8, |P< j+1 | ≤ M e2Aαd d = M e2Aα(j+1) = M e2Aα e2Aαj . d



(ii) j ≥ d. By Lemma 3.9, |P< j+1 | ≤ kd (1) 3 j+1 d d

d



≤ M eAαd 3 j+1 d

d



≤ M eAαd 10 dj

d

.

Since ln(10x) ≤ 3x for all x ≥ 1, we have d ln(10j/d) ≤ 3j ≤ 3αj. Thus, (10 dj )d ≤ e3αj , so ′ |P< j+1 | ≤ M eAαd e3αj . Combining this with Aαd ≤ Aαj, |P< j+1 | is strictly bounded by M eA αj . d

d

12

′

Since e2Aα > 1, in both cases, |P< j+1 | is upper bounded by M e2Aα eA αj . Therefore, by d

substituting C = 2A′ + 2, Cα j |P< j+1 | · exp − d 2 



′

′

≤ M e2Aα eA αj · e−(A +1)αj = M e2Aα e−αj ,

where the final inequality follows by choosing C sufficiently large. Plugging this into our original bound on Pr[P ∈ / P<γ ] yields a converging geometric series: Pr[P ∈ / P<γ ] ≤

∞ X j=k

M e2Aα e−αj ≤ M e2Aα

−αk e−αk 2Aα e ≤ M e ≤ 2M e2Aα e−αk . 1 − e−α 1 − e−1

Since k = ⌊γd⌋ ≥ γd − 1, we have e−αk ≤ e−α(γd−1) = eα e−αγd . Subtituting this into the above, we obtain Pr[P ∈ / P<γ ] ≤ 2M e2Aα e−αk ≤ 2M e2Aα eα e−αγd = 2M e(2A+1)α−αγd .

4

Low Randomness Mechanism for any ∥ · ∥K -norm

In this section, we use an MSSP partition to construct a low randomness ε-DP mechanism for any ∥ · ∥K -norm. To this end, we use the kd -MSSP partition P with respect to the ∥ · ∥K -norm from Theorem 3.2, where kd (ℓ) = O(d log d · ed/ℓ ); we set the scaling factor ρ = Cd/ε for a large constant C. Let r : P → Rd be the representative function. Theorem 4.1. Let ε > 0. Let f : X ∗ → Rd be such that sens∥·∥K (f ) ≤ 1. There is a mechanism that (i) is ε-DP, (ii) has expected ∥ · ∥K -error O(d/ε), and (iii) has randomness complexity O(log d). This immediately implies low randomness mechanisms for linear queries in the ℓp -norm. Corollary 4.2. Let p ≥ 1 and let ε > 0. Let f : X ∗ → Rd be such that sensℓp (f ) ≤ 1. There is a mechanism that (i) is ε-DP, (ii) has expected ℓp -error O(d/ε), and (iii) has randomness complexity O(log d). The mechanism in these results is described in Algorithm 2. In the rest of the section, we will prove the three properties of this mechanism, namely, privacy, utility, and randomness complexity. Algorithm 2 ExpPart: Exponential Partition Sampling Mechanism Input: Dataset X ∈ X ∗ Parameters: Norm ∥ · ∥K , function f : X ∗ → Rd , MSSP P, Privacy parameter ε, Representative function r : P → Rd satisfying r(P ) ∈ P for all P ∈ P Sample P ∈ P proportional to exp(− 2ε · ∆P (f (X))) return r(P )

13

▷ ∆P (x) = inf z∈P ∥x − z∥K

4.1

Privacy

We start by analyzing the privacy guarantee of Algorithm 2, which follows almost immediately from the definition and the privacy guarantee of the exponential mechanism. Lemma 4.3. ∆P (f (·)) has sensitivity at most 1 for any fixed P ; consequently, Algorithm 2 is ε-DP. Proof. Notice that Algorithm 2 is an instantiation of the exponential mechanism with scrP (X) := ∆P (f (X)). By Theorem 2.7, it suffices to show that scrP , i.e., ∆P ◦ f , has sensitivity at most 1. First, for any two points z1 , z2 ∈ Rd , and y ∈ P , we have by the triangle inequality ∥z1 − y∥K ≤ ∥z1 − z2 ∥K + ∥z2 − y∥K , and by taking infimum over y ∈ P on both sides and using the definition of ∆P , we have ∆P (z1 ) = inf ∥z1 − y∥K ≤ ∥z1 − z2 ∥K + inf ∥z2 − y∥K = ∥z1 − z2 ∥K + ∆P (z2 ). y∈P

y∈P

Thus, ∆P (z1 ) − ∆P (z2 ) ≤ ∥z1 − z2 ∥K . By symmetry, ∆P (z2 ) − ∆P (z1 ) ≤ ∥z1 − z2 ∥K as well, from which we obtain |∆P (z1 ) − ∆P (z2 )| ≤ ∥z1 − z2 ∥K , i.e., ∆P is Lipschitz. Now, consider any pair X ∼ X ′ of neighboring datasets. We have |∆P (f (X)) − ∆P (f (X ′ ))| ≤ ∥f (X) − f (X ′ )∥K ≤ 1 from the Lipschitzness of ∆P and since sens∥·∥K (f ) ≤ 1.

4.2

Utility

To analyze the expected utility of Algorithm 2, we note that ExpPart has two sources of error. The first comes from moving to a partition P rather than outputting f (x). This induces an error that is bounded by ∆P (f (x)), where P is a random variable. We will show that ∆P (f (x)) is fairly small in expectation since Lemma 3.10 guarantees that our mechanism usually outputs representative points of fairly close partition cells. The second source of error comes from r(·), which chooses a representative point within P ; this error is bounded by the scaling parameter ρ that we chose. 



 

Lemma 4.4. E[∆P (f (x))] = O logε d ; consequently, Algorithm 2 has expected ∥ · ∥K -error O dε . Proof. By Lemma 3.10, for some universal constants c1 , c2 and c3 = c2 /C, we have k−1 Pr[P ∈ / P<(k−1)/ρ ] ≤ d · exp −c2 d Cd/ε 

c1





= dc1 · exp(−c3 ε(k − 1)).







Let k ∗ = max ⌈ dρ ⌉ + 1, ⌈ c1c3lnε d ⌉ + 1 . Since dρ = Cε , we have k ∗ = O logε d . Now, note that the ∗

choice of k ∗ ensures that e−c3 ε(k −1) ≤ 1/dc1 and for k > k ∗ , we have (k − 1)/ρ ≥ 1/d. E[∆P (f (x))] ≤ ≤

∞ X k=0 k∗ X k=0



≤O

Pr[⌈∆P (f (x))⌉ > k] ≤

∞ X

Pr[∆P (f (x)) > k − 1] ≤

k=0 ∞ X

1+

dc1 · e−c3 ε(k−1) ≤ k ∗ + 1 +

log d ε

+O

∞ X j=0

1 ε

 

=O



Pr[P ∈ / P<(k−1)/ρ ]

k=0

k=k∗ +1



∞ X

e−c3 εj = k ∗ + 1 +

1 1 − e−c3 ε

log d . ε 

The total expected error isthe  sum of the maximum cell diameter (2ρ) and the expected distance, d i.e., 2ρ + E[∆P (f (x))] = O ε , from our choice of ρ. 14

4.3

Randomness Complexity

By Theorem 2.10, it suffices to bound the output entropy of our mechanism. This in turn is upper bounded by the entropy of P , the random partition cell chosen by the mechanism. Lemma 4.5. H(P ) = O(log d); consequently, Algorithm 2 has randomness complexity O(log d). Proof. Let Z = ⌈d · ∆P (f (x))/ρ⌉. Note that if Z = k, then P ∈ P<(k+1)/d . Applying Lemma 4.4, 

E[Z] = E

d·

∆P (f (x) ρ



=O



d log d E[∆P (f (x))] = O(ε) · O ρ ε 





= O(log d).

We first bound H(P | Z). Given Z = k, the mechanism outputs a cell from P<(k+1)/d . For k ≤ d, the MSSP guarantee yields |P<(k+1)/d | ≤ O(d log d · ek+1 ), i.e., log |P<(k+1)/d | = O(log d) + O(k). For k > d, Lemma 3.9 yields |P<(k+1)/d | ≤ dO(1) · ed · (3(k + 1)/d)d , i.e., log |P<(k+1)/d | = O(d log k). Thus, H(P | Z) = ≤ ≤

∞ X k=1 ∞ X k=1 d X

Pr[Z = k] · H(P | Z = k) Pr[Z = k] · log |P<(k+1)/d | ∞ X

Pr[Z = k] · O(log d) + O(k) +

k=1

≤ O(log d) ·

Pr[Z = k] · O(d log k)

k=d+1 ∞ X

Pr[Z = k] + O(1) ·

k=1

∞ X

k Pr[Z = k] + O(1)

k=1

= O(log d) + O(E[Z]) + O(1) = O(log d). (The O(1) follows because Pr[Z = k] decays exponentially as e−Ω(k) by Lemma 3.10, which dominates the polynomial O(d log k) term for k > d.) Next, we bound H(Z). Using the well known information-theoretic fact that for any random variable X with support on Z≥0 , H(X) ≤ E[X] + O(1) [GPS13], we obtain H(Z) ≤ E[Z] + O(1) = O(log d). Therefore, H(P ) ≤ H(Z) + H(P | Z) = O(log d).

5

Efficient Mechanism for ℓ∞ -norm

Using the MSSP from Theorem 3.7 and the same reasoning as in the proof of Theorem 4.1 implies a mechanism that uses O(log d) bits of randomness. However, the resulting mechanism is not immediately “efficient”. In this section, we show the following. Theorem 5.1. Let ε ≤ log d. Let f : X ∗ → Qd be such that sens∥·∥∞ (f ) ≤ 1. There is a mechanism that (i) is ε-DP, (ii) has expected ∥·∥∞ -error O((d log d)/ε), (iii) has expected randomness complexity O(log d), and (iv) has expected running time poly(T (f, X), 1/ε), where T (f, X) denotes the time required to evaluate f on input X. Let c = ⌈log(4eε/2 /ε)⌉, a = ⌈2c e−ε/2 ⌉ and choose ε′ so that ′

λ = e−ε /2 = 15

a . 2c

Note that λ can be represented in binary using only c bits; also, it is easy to see that ε/2 ≤ ε′ ≤ ε. To make sampling computationally easier, we will show that our mechanism is ε′ -DP. Throughout this section, P will refer to the partition induced by Algorithm 1 scaled so that d ρ = C d log for some sufficiently large constant C. Let B = 7, the constant in the exponent of Nm ε from Lemma 5.3. The high-level idea of our efficient mechanism is as follows. We wish to sample from a distribution with probabilities proportional to exp(− 2ε ∆P (f (X))) efficiently (actually, we sample from exp(− 2ε ⌈∆P (f (X))⌉) for technical bit-complexity reasons). We will do so by first using some randomness to determine how large ∆P (f (X)) should be. This gives us an annulus from which we should sample P . We then enumerate the partitions in this annulus and use more randomness to select one among them.

5.1

Efficiently Enumerating Partitions

We first describe two algorithms that will be crucial to Algorithm 3. The first is for computing ∆P (f (X)) = inf y∈P ∥f (X) − y∥∞ efficiently, where the challenge is due to the infimum. We then use this to design a second algorithm that efficiently enumerates the partition cells that are close (for some definition of “close”) to a particular point. For a ∈ {0, . . . , d − 1} and z ∈ Zd , let Pa,z ∈ P denote the partition cell whose representative point is (z1 + a/d, . . . , zd + a/d). Lemma 5.2. There is an algorithm that given v ∈ Qd and a ∈ {0, . . . , d − 1}, z ∈ Zd , computes ∆Pa,z (v) in time polynomial in the input length. Proof. We use the notation from Algorithm 1. We now obtain a precise characterization of the points in Pa,z . It is easy to see that each y ∈ Pa,z must be of the form yi = zi +

a + ti d

where 0 ≤ ti < 1.

(2)

Therefore, an exact characterization of Pa,z is the set of points y ∈ Rd such that (2) holds and A(y) = a. Lemma 3.4 tells us that the latter condition is exactly 1. For b < a, Φa (y) < Φb (y) (equivalently, Cm < m), and 2. For b > a, Φa (y) ≤ Φb (y) (equivalently, Cm ≤ m), where m = (a − b) mod d and Cm = |{i : ti ≥ 1 − m/d}|). Indeed, if Φa (y) ≥ Φb (y) for any b < a, then A(y) ̸= a by our choice of tie-breaking rule in Algorithm 1. Similarly, if Φa (y) > Φb (y), then A(y) ̸= a. The equivalent conditions Cm < m and Cm ≤ m follow by unpacking the definition of Φb − Φa in Lemma 3.4. Therefore, an exact characterization of Pa,z is the set of points y ∈ Rd such that (2) holds and |{i : ti ≥ 1 − m/d}| < m for all m ∈ [0, a] and |{i : ti ≥ 1 − m/d}| ≤ m for all m ∈ [a + 1, d − 1]. Equivalently6 , we may write the constraints on the coordinates ti as 0 ≤ ti < 1 and once the ti ’s are sorted as t(1) , . . . , t(d) , then t(d−m+1) ≤ 1 − m/d for m ≤ a and t(d−m) ≤ 1 − m/d for m > a. Let T be the set of points (t1 , . . . , td ) satisfying these constraints. Now, consider. a ∆P (v) = inf max |vi − yi | = inf max vi − zi + + ti y∈P i∈[d] t∈T i∈[d] d 

6



= inf max|wi − ti |, t∈T i∈[d]

This equivalence is true up to boundary points, which will not change the final result.

16

where wi = vi − (a/d) − zi . Let π : [d] → [d] be the permutation that orders w1 , . . . , wd . We now show that we may assume tπ(1) ≤ · · · ≤ tπ(d) . Indeed, if ti < tj and wi > wj , we may safely swap ti and tj without increasing since max(|ti − wi |, |tj − wj |) ≥ max(|tj − wi |, |ti − wj |). Therefore, we must minimize r = ∆P (v) under the following constraints. 1. −r ≤ wi − ti ≤ r for all i ∈ [d] 2. 0 ≤ ti < 1 for all i ∈ [d] 3. tπ(1) ≤ · · · ≤ tπ(d) 4. tπ(d−m+1) ≤ 1 − m/d for all m ∈ [0, a] 5. tπ(d−m) ≤ 1 − m/d for all m ∈ [a + 1, d − 1] This is a linear program with poly(d) variables and constraints, each of which can be represented using polynomially many bits, and can therefore be solved in time polynomial in the input length. Next, we show a bound on the number of cells in a certain annulus. Lemma 5.3. For every v ∈ Qd , every m ≥ 0, and τ = ρ/d, the number of cells P ∈ P with mτ ≤ ∆P (v) ≤ (m + 1)τ is at most Nm = (d + 1)7(m+2) . Moreover, these cells can be enumerated in time poly(d) · Nm . Proof. If ∆P (v) ≤ (m + 1)τ, then P intersects the larger ball B := B∞ (v; sτ ), where s = m + 2. Hence, it suffices to enumerate all cells that intersect B, i.e., for each fixed a, to bound and enumerate 



Wa = B ∩ 

[

Pa,z .

z∈Zd

Define Fi (a) =



yi a :y∈B . − ρ d 



Since B has ℓ∞ -radius sτ = sρ/d, the interval of possible values of yi /ρ has length 2s/d. We consider two cases depending on s. (i) Case s ≤ d/3. Then 2s/d < 1, so each Fi (a) has size at most 2. Suppose Pa,z ∩ B = ̸ ∅, and choose y ∈ Pa,z ∩ B. For every coordinate i with |Fi (a)| = 2, write Fi (a) = {ri , ri + 1}. Let E(z) = {i : |Fi (a)| = 2 and zi = ri }. Thus E(z) is the set of coordinates where z chooses the lower of the two possible floor values. If i ∈ E(z), then yi realizes the lower floor value, while some point of B realizes the upper floor value. Since the coordinate width of B is 2sτ , this implies 

yi a − ρ d



≥1−

2s . d

Because y ∈ Pa,z , the chosen shift of y is a. By Lemma 3.5, |E(z)| ≤ 2s + 1. For fixed a, the vector z is determined by E(z): coordinates with |Fi (a)| = 1 have no choice, and coordinates with |Fi (a)| = 2 choose the lower value exactly on E(z). Hence the number of candidates for this shift is at most 2s+1 X j=0

!

d j

≤ (d + 1)2s+1 . 17

Therefore, |Wa | ≤ (d + 1)2s+1 . These candidates are enumerated by looping over a and all subsets E ⊆ [d] of size at most 2s + 1. (ii) Case: s > d/3. Here we use the crude product enumeration. For fixed a, each coordinate yi has at most 2s d + 3 possible floor values for ⌊yi /ρ − a/d⌋. Therefore, the number of candidate vectors R(y) for this shift is at most  d 2s +3 . d Since for all x ≥ 1/3, ln(2x + 3) ≤ 4x, 

d 2s + 3 ≤ e4s ≤ (d + 1)6s . d



The candidates are enumerated by looping over all ≤ (d + 1)6s possible combinations of coordinate floor values. Combining the two cases and enumerating over all choices of a, the number of cells intersecting B is at most d·(d+1)6s < (d+1)7(m+2) = Nm . After enumerating these cells, we use Lemma 5.2 to compute ∆P (v) exactly in time poly(d) and retain only those cells satisfying mτ ≤ ∆P (v) ≤ (m + 1)τ .

5.2

Sampling Algorithm

The key technique we use is that of rejection sampling. Let τ = ⌈ Cε · log(d + 1)⌉ for a sufficiently large absolute constant C and set ρ = dτ . Choose C so that ετ ≥ 400B · log(d + 1). Notice that we have chosen τ so that λτ ≤ e−100B·log(d+1) = (d + 1)−100B . We define several annuli of grid cells depending on their distance from v. These annuli partition the grid cells into disjoint sets: L0 = {P : ⌈∆P (v)⌉ ≤ τ },

Lm = {P : mτ < ⌈∆P (v)⌉ ≤ (m + 1)τ }.

Define wP := λ⌈∆P (v)⌉ . We first enumerate L0 and compute W0 =

X

wP .

P ∈L0

Note that since the cell containing v has ⌈∆P (v)⌉ = 0, W0 ≥ 1. For m ≥ 1, let Um = Nm λmτ = (d + 1)B(m+2) λmτ , Finally, set S=

X m≥1

Um =

γ=

Um+1 = (d + 1)B λτ ≤ (d + 1)−99B . Um

(d + 1)3B λτ , 1 − (d + 1)B λτ

18

and

U = W0 + S.

(3)

Algorithm 3 Efficient Partition Sampler Require: Dataset X ∈ X ∗ Parameters: Function f : X ∗ → Rd , Privacy parameter ε, Representative function r : P → Rd while true do b0 ∼ Ber(W0 /U ) if b0 = 1 then Sample a cell P ∈ L0 with probability wP /W0 return r(P ) M ← Geom(1 − γ)

▷ Step 1: Possibly sample from L0 ▷ Use Lemma 2.11 repeatedly ▷ Step 2: Sample M

Enumerate LM = {P1 , . . . , Ph } Sample J ∼ Uniform([NM ])

▷ Step 3: Possibly sample from LM

if J ≤ h then p ← λ⌈∆PJ (f (X))⌉−M τ b1 ∼ Ber(p) if b1 = 1 then return r(PJ ) We use Geom(p) to denote the geometric distribution over Z>0 where k appears with probability p(1 − p)k−1 . This can be sampled from by repeatedly sampling from Ber(p) and return the index of the first sample that equals 1, which takes 1/p samples from Ber(p) in expectation. Lemma 5.4. Algorithm 3 outputs P ∈ P with probability proportional to exp(− 2ε ⌈∆P (f (X))⌉). Proof. Suppose P ∈ L0 . In one round, the probability of proposing L0 and then choosing P ∈ L0 is W 0 wP wP · = . U W0 U Now suppose P ∈ Lm , for some m ≥ 1. From (3), γ m−1 = Um /U1 , S = U1 /(1 − γ), and γ m−1 (1 − γ) = Um /S. In one round, the probability of proposing Lm , selecting P , and accepting is S 1 S Um 1 · γ m−1 (1 − γ) · · λ(⌈∆P (f (X))⌉−mτ ) = · · · λ(⌈∆P (f (X))⌉−mτ ) U Nm U S Nm λmτ λ⌈∆P (f (X))⌉ wP Um = · λ(⌈∆P (f (X))⌉−mτ ) = · λ(⌈∆P (f (X))⌉−mτ ) = = . U · Nm U U U Therefore, the probability of outputting P over all rounds is proportional to wP . We prove a useful fact that for any sequence {Ct }t∈N of random variables parameterized by and depending on round t of Algorithm 3, E[C1 ] is a fairly good estimate of the expectation of the sum of random variables. We then use this fact to bound the expected number of random bits consumed by our algorithm as well as the expected running time.

19

Lemma 5.5. Let {Cet }t∈N be a sequence of integer random variables where Cet depends only on the randomness that would be used during round t of Algorithm 3 (if round t were executed) and let Ct = Cet if round t of Algorithm 3 executes and 0 otherwise.   X E Ct  = O(E[C1 ]). t≥1

Proof. Let Et denote the event that round t of the sampling algorithm results in an accepting computation (i.e., sampling happens and no restart occurs) and p = Pr[Et ] (note that the probability is the same across every round). Let N = mint 1Et ; clearly, Pr[N ≥ t] = (1 − p)t−1 . Note that Ct = Cet · 1N ≥t and E[Cet ] = E[C1 ].     X X X X E[C1 ] E Ct  = E Cet · 1N ≥t  = E[Cet ] · Pr[N ≥ t] = E[C1 ] (1 − p)t−1 = . t≥1

t≥1

r≥1

p

t≥1

Therefore, it suffices to show that p = Θ(1). By Lemma 5.6, the probability in any round of outputting P is wP /U , the acceptance probability in each round is p=

⌈∆P (f (X))⌉ P ∈P λ

P

U

=

P

P ∈P λ

⌈∆P (f (X))⌉

W0 + S

≥

W0 1 ≥ = Ω(1), W0 + S 1+S

where the final inequality follows from (3) that limd→∞ S = 0.

5.3

Privacy

We show that Algorithm 3 samples from the correct distribution and is therefore ε-DP. Lemma 5.6. Algorithm 3 is ε-DP. Proof. Since f has sensitivity at most 1, by Lemma 4.3, ∆P (f (X)) and hence ⌈∆P (f (X))⌉ has sensitivity at most 1. Thus, from Lemma 5.4, the ε-DP property follows.

5.4

Utility

The analysis of the total error is similar to that of Lemma 4.4. Lemma 5.7. For P sampled with probability proportional to exp(− 2ε ⌈∆P (f(X))⌉), it holds that   d E[∆P (f (X))] = O logε d ; consequently, Algorithm 3 has expected ℓ∞ -error O d log . ε

Proof. This lemma is essentially the same as Lemma 4.4, we reiterate that argument for completeness. By Theorem 3.7, we have kd (ℓ) ≤ (ℓ + 1)O(d/ℓ) ≤ eO(d log d/ℓ) . Then, by Lemma 3.10 applied with α = log d, for some universal constants c1 and c3 = 1/C, we have 

Pr[P ∈ / P<(k−1)/ρ ] ≤ exp c1 log d − log d · d 



k−1 Cd log d/ε



= dc1 · exp(−c3 ε(k − 1)). 



log d d ∗ Let k ∗ = max ⌈ dρ ⌉ + 1, ⌈ c1c3lnε d ⌉ + 1 . Since dρ = C log . Now, note that the ε , we have k = O ε ∗

choice of k ∗ ensures that e−c3 ε(k −1) ≤ 1/dc1 and for k > k ∗ , we have (k − 1)/ρ ≥ 1/d. E[⌈∆P (f (X))⌉] =

∞ X k=0

Pr[⌈∆P (f (X))⌉ > k] ≤

∞ X

Pr[∆P (f (X)) > k − 1] ≤

k=0

20

∞ X k=0

Pr[P ∈ / P<(k−1)/ρ ]

∗

≤

k X

≤O

dc1 · e−c3 ε(k−1) ≤ k ∗ + 1 +

k=k∗ +1

k=0



∞ X

1+ log d ε



+O

∞ X

e−c3 εj = k ∗ + 1 +

j=0

1 ε

 

=O



1 1 − e−c3 ε

log d . ε 

Since the expected ℓ∞ error of Algorithm 3 is at most 2ρ+∆P (f (X)), substituting ρ = C ·d log d/ε and the above bounds lets us conclude that Algorithm 3 has expected ℓ∞ error at most O(d log d/ε).

5.5

Randomness Complexity

Lemma 5.8. Algorithm 3 has randomness complexity O(log d). Proof. Let R1 denote the number of random bits used in round 1 of the sampling algorithm. By Lemma 5.5, the expected number of random bits used by the sampler is O(E[R1 ]). It therefore suffices to upper bound E[R1 ]. We write R1 = K1 + K2 + K3 , where K1 , K2 , K3 denote the number of random bits used in steps 1, 2, and 3 of the sampling algorithm respectively. First, E[K1 ] = O(log d) since N0 = poly(d) and we can choose P ∈ N0 by O(log d) calls to Lemma 2.11, using each call to decide which half of the remaining cells of N0 to sample from. Next, K2 is geometrically distributed with parameter 1 ) = O(1). O(1 − γ) and therefore, E[K2 ] = O( 1−γ Finally, E[K3 ] = E [E[K3 | M = m]]. Since we require log(Nm ) bits to sample from [Nm ] and m∼M

O(1) bits to sample Ber(p), by Lemma 2.11, E[K3 | M = m] = log(Nm ) + O(1) = 7(m + 2) log(d + 1) + O(1) = O(m log d). Therefore, 1 E[K3 ] = O E [m log d] = O(log d · E[M ]) = O log d · m∼M 1−γ 







= O(log d).

So, E[R1 ] = E[K1 ] + E[K2 ] + E[K3 ] = O(log d), as desired.

5.6

Running Time

Lemma 5.9. Let T (f, X) denote the time to evaluate f on input X; consequently, Algorithm 3 has expected running time poly(T (f, X), 1/ε). Proof. By Lemma 5.5, it suffices to bound O(E[C1 ]). Let |·|b denote the bit-length and T := T (f, X). Let K1 , K2 , K3 denote the amount of time spent in steps 1, 2, and 3 of Algorithm 3 respectively; we will bound these separately. To bound K1 , note that we would spend poly(d) time in step 1 if all operations were over real numbers. Furthermore, the computation of each ⌈∆P (f (X))⌉ can be done in time polynomial in the length of T and d (which is poly(T )) by Lemma 5.2. Since these quantities are rational numbers with denominator ≤ (2c )|⌈∆P (f (X))⌉|b ≤ 2polylog(1/ε)·poly(T ) , we can perform bit operations with overhead bounded above by poly(T, 1/ε). Therefore, E[K1 ] ≤ poly(T, 1/ε).

21

To bound K2 , we observe that we may write K2 = ∞ j=1 Rj , where Rj denotes the bit complexity of round j of step 2 (where Rj = 0 if the process has terminated). P

E[Rj ] = E[Rj | Rj > 0] · Pr[Rj > 0] = E[Rj | Rj > 0] · γ j−1 = poly(d, 1/ε, log j) · γ j−1 . From this, E[K2 ] =

∞ X

E[Rj ] = poly(d, 1/ε)

j=1

∞ X

polylog(j) · γ j−1 = poly(d, 1/ε).

j=1

To bound E[K3 ], we compute E[K3 | M = m]. By Lemma 5.3, Lm can be enumerated in time poly(d) · Nm = poly(d) · (d + 1)B(m+2) and choosing J can be done in (expected) time poly(log Nm ) = poly(m, log d). Next, consider the bit complexity of ⌈∆Pj (f (X))⌉. This quantity is computed by a polynomial time call to the subroutine Lemma 5.2 with input f (X) and a, z representing Pj ; this yields |f (X)|b ≤ T and |a, z|b ≤ poly(τ m) = poly(1/ε, log d, m). Hence, ⌈∆ (f (X))⌉ ⌈∆Pj (f (X))⌉ ≤ poly(T, 1/ε, m) and |λ Pj |b = poly(T, 1/ε, m). Therefore, p can be sampled in expected time poly(T, 1/ε, m). Together, E[K3 | M = m] = poly(T, 1/ε, m) · (d + 1)B(m+2) . E[K3 ] = = ≤ ≤

∞ X m=1 ∞ X m=1 ∞ X m=1 ∞ X

E[K3 | M = m] · Pr[M = m] poly(T, 1/ε, m) · (d + 1)B(m+1) · γ m−1 (1 − γ) poly(T, 1/ε, m) · (d + 1)B(m+2) · γ m−1 poly(T, 1/ε, m) · (d + 1)B(m+2) · (d + 1)B(m−1) (d + 1)−100B(m−1)

m=1

≤ poly(T, 1/ε) +

∞ X

poly(T, 1/ε, m) · (d + 1)−m = poly(T, 1/ε).

m=1

6

Conclusion and Open Questions

We give an ε-DP algorithm for answering d linear queries with nearly optimal error and randomness complexity, which (essentially) resolves the main open questions from [CSV25]. Despite this progress, there are several obvious remaining gaps, which we highlight below. • As mentioned earlier, our randomness complexity of O(log d) is only known to be tight in the regime where ε ≤ 1/d. Moreover, our efficient mechanism has ℓ∞ -error O(d log d/ε) which is a factor of O(log d) off from the optimal bound. • Our algorithms are only efficient for the ℓ∞ -sensitivity case. It would be interesting to obtain efficient algorithms for all K-norms, or at least all ℓp -norms. • While not the focus of our paper, we do obtain improvements for approximate-DP (i.e., (ε, δ)-DP) over the previous algorithms [CSV25, Ghe26] as well. Without a constraint on p randomness complexity, the optimal ℓ∞ -error is O( d log(1/δ)/ε) [SU16, DK22, GKM21]. If we restrict the worst case number of random bits to (log d)O(1) , then the approximate-DP

22

e 1.5 /ε), which is worse than our mechanisms from [CSV25, Ghe26] incur ℓ∞ -error of at least Ω(d √ e d) between our pure-DP algorithm with O(d/ε) error. Nevertheless, there is still a gap of Ω( error bound and the upper bound without any worst-case randomness complexity constraint. Finally, we remark that the study of DP algorithms under the lens of randomness complexity is still nascent, and a large number of problems are yet to be explored. Specifically, one could take any fundamental DP problem and examine its randomness complexity vs utility tradeoff.

AI Disclosure Statement Gemini 3.1 Pro and GPT 5.5 Pro were used for several parts of this manuscript. The authors defined a multi-scale secluded-partition (MSSP) and observed that such objects may be used to obtain particularly low randomness DP mechanisms. AI was used to construct a good MSSP for the ℓ∞ -norm, which it did by modifying the construction of Hoza and Klivans [HK18]. The authors confirmed the correctness of this construction by formalizing it in Lean4 using an AI coding agent (Google Antigravity). The authors then observed that an efficient mechanism could be obtained using the ring sampling technique described in § 5, which AI was used to formalize. AI was also used to generate the Rogers [Rog57] inspired construction in § 3.1. AI was used to generate drafts of almost all proofs, which the authors then iterated over. AI was also used to generate Figure 1 and check proofs for errors. The authors verified the correctness and originality of all content and are ultimately responsible for any oversight.

References [CSV25]

Clément L. Canonne, Francis E. Su, and Salil P. Vadhan. The Randomness Complexity of Differential Privacy. In ITCS, pages 27:1–27:21, 2025. i, 1, 2, 5, 22, 23

[DK22]

Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. In COLT, pages 625–661, 2022. 22

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265–284, 2006. 1, 5 [ER62]

P Erdos and C. A. Rogers. Covering space with convex bodies. Acta Arithmetica, 7(3):281–285, 1962. 9

[Ghe26]

Surendra Ghentiyala. Efficient derandomization of differentially private counting queries. In SOSA, pages 192–215, 2026. i, 1, 6, 22, 23

[GKM21]

Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On avoiding the union bound when answering multiple differentially private queries. In COLT, pages 2133–2146, 2021. 22

[GL20]

Simson L. Garfinkel and Philip Leclerc. Randomness concerns when deploying differential privacy. In WPES, pages 73–86, 2020. 1

[GPS13]

Solomon W Golomb, Robert E Peile, and Robert A Scholtz. Basic Concepts in Information Theory and Coding: the Adventures of Secret Agent 00111. Springer Science & Business Media, 2013. 15 23

[GRS12]

Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utilitymaximizing privacy mechanisms. SIAM J. Comput., 41(6):1673–1693, 2012. 1

[HK18]

William M. Hoza and Adam R. Klivans. Preserving randomness for adaptive algorithms. In APPROX/RANDOM, 2018. 4, 23

[HT10]

Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705–714, 2010. i, 1, 4

[Joh48]

Fritz John. Extremum problems with inequalities as subsidiary conditions, studies and essays presented to R. Courant on his 60th birthday, January 8, 1948, 1948. 5

[KP26]

Nikita P Kalinin and Rasmus Pagh. Dithered gaussian mechanism for randomnessefficient differential privacy. arXiv preprint arXiv:2607.06320, 2026. 1

[KY76]

Donald E. Knuth and Andrew C. Yao. The complexity of nonuniform random number generation. In Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), pages 357–428. Academic Press, New York, 1976. 2, 6

[MT07]

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In FOCS, pages 94–103, 2007. 3, 5

[Pis99]

Gilles Pisier. The Volume of Convex Bodies and Banach Space Geometry. Cambridge University Press, 1999. 4

[Rog57]

C. A. Rogers. A note on coverings. Mathematika, 4(1):1–6, 1957. 9, 23

[SU16]

Thomas Steinke and Jonathan R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2016. 1, 22

[TV06]

Terence Tao and Van H Vu. Additive Combinatorics. Cambridge University Press, 2006. 5

[WDP+ 22] Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Geometry of rounding. CoRR, abs/2211.02694, 2022. 2, 3, 4 [WDP+ 23] Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Geometry of rounding: Near optimal bounds and a new neighborhood Sperner’s lemma. CoRR, abs/2304.04837, 2023. 2, 3, 4 [WDP+ 24] Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Replicability in learning: Geometric partitions and KKM-Sperner lemma. In NeurIPS, 2024. 2

24

Related documents

• Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries#924996
• Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries#920762
• Differentially Private Datastore Generation for Retrieval-Augmented Inference#246440
• LAPRAS : Learning-Augmented PRivate Answering for linear query Streams#155416
• Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant#144165