arXiv CSopen access

The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting Konstantina Bairaktari∗

Kasper Green Larsen∗

arXiv:2607.00876v1 [cs.DS] 1 Jul 2026

Abstract Private continual counting is a fundamental problem in differential privacy: given a binary stream of length n, where each 1 corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected ℓ∞ error proportional to log3/2 n for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on n by proving that every differentially private mechanism for continual counting must incur expected ℓ∞ error Ω(log3/2 n). This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private ℓ∞ error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.

1

Introduction

How can an organization track the occurrence of sensitive events over time without compromising the privacy of individuals? Such scenarios arise naturally in many settings, including monitoring daily disease cases, counting user interactions on a platform, or measuring responses to a public poll. This motivates the study of private continual counting, the focus of this paper. The standard formulation of the problem models time as discrete steps 1, . . . , n, where at each step a bit indicates whether an event occurred. Each 1 corresponds to the contribution of one individual and each individual participates in at most one event. The goal is to release an accurate running count at every time step without revealing any individual’s contribution. The study of private continual counting was initiated by [DNPR10, CSS10], who established the foundations for differentially private computations under continual observation. Differential privacy (DP) [DMNS06] is the standard framework for formal privacy guarantees, ensuring that the output of a mechanism reveals little about any individual’s data. Private continual counting has found applications in a broad range of tasks including private online learning [JKT12, TS13], convex optimization [AFKT21] and federated learning [KMS+ 21]. In many of these applications, it appears as a subroutine, and improving its accuracy directly translates to improvements in the downstream task. The appropriate notion of error, however, depends on the application: ℓ∞ error (the expected worst-case error over all time steps) is a natural measure for monitoring tasks, while ℓ2 error (the expected root mean squared error over all time steps) is more relevant for learning applications [HUU23]. In this work, we focus on the ℓ∞ error. The most well-known method for private continual counting is the binary tree mechanism [DNPR10, CSS10], which computes carefully structured subset counts in a differentially private manner and combines them to recover the running count at any given time step. ∗ Department of Computer Science, Aarhus University. Supported by the European Union (ERC, TUCLA, 101125203). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

1

For pure differential privacy, the binary tree mechanism uses Laplace noise to make the subset counts ε-differentially private. Here, and throughout the paper, we focus on the regime where ε ∈ (0, 1). While the original analysis achieves ℓ∞ error O(log5/2 (n)/ε) [DNPR10, CSS10], a more careful analysis of the same algorithm yields an improved bound of O(log2 (n)/ε). The best known lower bound is Ω(log(n)/ε) [DNPR10], leaving a multiplicative gap of log n. For approximate DP, the binary tree mechanism uses Gaussian p noise instead of Laplace, yielding an (ε, δ)-differentially private mechanism with ℓ∞ error O(log3/2 (n) log(1/δ)/ε) [JRSS23]. Prior to our work, the best known lower bound related to the ℓ∞ error under approximate DP was an Ω(log(n)/ε) lower bound p on the square root of the expected value of the square of the worst-case error over all n time steps ( ℓ2∞ error) [FHU23]. Whether the ℓ∞ error upper bounds are tight in the dependency on the stream length n has remained an important open problem. In this work, we resolve the approximate DP setting by proving a lower bound of Ω(log3/2 (n)/ max{ε, δ}). For δ = 0, this applies to pure DP, tightening the gap there as well. Table 1 summarizes the best known upper and lower bounds for pure and approximate DP with ε ∈ (0, 1). Setting

Error Notion

Upper Bound

Lower Bound

2

Pure DP

ℓ∞ error

log (n)/ε

Approx. DP

ℓ∞ error p ℓ2∞ error

log3/2 (n) log1/2 (1/δ)/ε [JRSS23]

log

3/2

(n)/ε [Our result]

log3/2 (n)/ max{ε, δ} [Our result] log(n)/ε [FHU23]

Table 1: Best known asymptotic lower and upper bounds under pure and approximate DP for 0 < ε < 1 and 0 < δ < C for a small constant C > 0. Before stating our result, we formally define the problem of private continual counting and the privacy notion we work with. Let x ∈ {0, 1}n be the binary input vector, where xi = 1 indicates that an event occurred at time step i and since the mechanism operates in an online fashion, at time step i only Pthe entries x1 , . . . , xi are visible to it. The goal is to approximate, at each time step i, the running count j≤i xj in a differentially private manner. These n running counts can be written compactly as Ax, P where A is the n × n lower triangular matrix of all ones, known as the prefix-sum matrix, with (Ax)i = j≤i xj . This problem can be seen as a specific instance of linear queries (mechanisms that answer queries of the form Ax for a fixed matrix A), where the query matrix is the prefix-sum matrix A. A private mechanism M must output a vector M(x) ∈ Rn , where M(x)i is the estimate released at time step i, so that ∥M(x) − Ax∥∞ is small while ensuring privacy of any individual’s entry in x. With this notation, the ℓ∞ error is E[∥M(x) − Ax∥∞ ], whereas the ℓ2 error is n−1/2 E[∥M(x) − Ax∥2 ]. We say that two binary vectors x, x′ ∈ {0, 1}n are neighboring if they differ in exactly one coordinate. The mechanism M is required to satisfy differential privacy, defined as follows. Definition 1 (Differential Privacy [DMNS06]). Fix ε > 0 and δ ∈ [0, 1). A mechanism M is (ε, δ)-DP if for any measurable set S ⊆ Rn , Pr[M(x) ∈ S] ≤ eε Pr[M(x′ ) ∈ S] + δ for all pairs of neighboring inputs x, x′ ∈ {0, 1}n . The case where δ = 0 is referred to as pure DP and the case where δ > 0 is referred to as approximate DP. Our main result establishes a fundamental lower bound on the ℓ∞ error of any (ε, δ)-DP mechanism for continual counting. Theorem 1. For any 0 < ε < 1, 0 < δ < C for a sufficiently small constant C > 0, it holds that any

2

(ε, δ)-DP mechanism M for continual counting has error max E[∥M(x) − Ax∥∞ ] = Ω

x∈{0,1}n

log3/2 n max{ε, δ}

! ,

where A is the n × n prefix-sum matrix. This shows that the binary tree mechanism has an asymptotically optimal dependency on n in the approximate DP setting. We now make a few observations about the lower bound in Theorem 1. The binary tree mechanism can operate in both the continual observation model, where the input stream arrives online, and the offline observation model [CLN+ 24], where the mechanism receives the entire input stream at once. Our lower bound holds in the offline observation model and, since any mechanism for continual observation also yields a mechanism for offline observation, lower bounds in the offline model imply lower bounds for the continual observation model. Specifically, such lower bounds emphasize that the hardness comes from releasing n outputs privately rather than one. Maximum Separation Between Privacy and Hereditary Discrepancy. As an interesting corollary of Theorem 1, we also derive the largest possible separation between hereditary discrepancy and the error of (ε, δ)-DP mechanisms for linear queries. Recall that continual counting, or prefix sums, can be seen as a special case where A is the n × n prefixsum matrix. More generally, for an arbitrary query matrix A ∈ Rm×n , a well-studied task is to design a private mechanism M(x) for releasing an approximation of Ax for x ∈ {0, 1}n . Let errε,δ ∞ (A) denote the smallest achievable ℓ∞ error of an (ε, δ)-DP mechanism M: errε,δ ∞ (A) :=

max E[∥M(x) − Ax∥∞ ].

inf

M:M is (ε,δ)-DP x∈{0,1}n

The quantity errε,δ ∞ (A) is known to be closely related to the notion of hereditary discrepancy. The discrepancy of an m × n matrix A, denoted disc∞ (A), is defined as disc∞ (A) = minx∈{−1,1}n ∥Ax∥∞ . If S ⊆ [n] denotes a subset of column indices and A|S the matrix A restricted to the columns indexed by S then herdisc∞ (A) := max disc(A|S ). S⊆[n]

The ellipsoid mechanism M of Nikolov, Talwar and Zhang [NTZ13] can be analyzed through the factorization norm framework of Matousek, Nikolov and Talwar [MNT20] to guarantee   p max n E[∥M(x) − Ax∥∞ ] = O ε−1 log m · log(1/δ) · γ2 (A) , x∈{0,1}

where γ2 (A) is the γ2 factorization norm of A. It was further shown in [MNT20] that γ2 (A) = O(log m · herdisc∞ (A)). Combining it all gives p −1 errε,δ log3/2 m · log(1/δ) · herdisc∞ (A)). ∞ (A) = O(ε 3/2 Ignoring the ε and δ dependencies, this is errε,δ m·herdisc∞ (A)). At the same time, [NTZ13] ∞ (A) = Oε,δ (log ε,δ showed that err∞ (A) = Ωε,δ (herdisc∞ (A)/ log m) (with a slight twist in the lower bound requiring the definition of herdisc∞ (A) to be only over S ⊆ [n] of linear size). In summary, there is a constant Cε,δ > 0 (depending on ε and δ) such that 3/2 herdisc∞ (A)/(Cε,δ log m) ≤ errε,δ m. ∞ (A) ≤ Cε,δ herdisc∞ (A) log

If A denotes the prefix-sum matrix, we have herdisc∞ (A) = 1. Our lower bound in Theorem 1 thus shows 3/2 that the general upper bound errε,δ m) cannot be improved. Prior to our ∞ (A) = Oε,δ (herdisc∞ (A) log work, the largest separation was a factor log m, obtainable from prior lower bounds for prefix sums. 3

Overview. We now outline the proof of Theorem 1. To simplify the task, we first use a reduction from prior work [BDKT12] that allows us to assume that the mechanism M is oblivious, meaning that M(x) = Ax + z for a noise vector z independent of x, but possibly with correlations between its coordinates. We thus need to prove that E[∥z∥∞ ] = Ω(log3/2 (n)/ max{ε, δ}). The proof has two main parts. In the first part, we express the noise vector in a basis induced by a binary tree and show that the noise necessarily accumulates along root-to-leaf paths, converting the task of lower bounding E[∥z∥∞ ] into lower bounding a weighted sum of local residual noise contributions in the tree. In the second part, we use a privacy argument: if all these residual noise contributions were too small, we could construct an adversary that distinguishes neighboring inputs by projecting the output of the mechanism onto a carefully chosen collection of vectors we call linear measurements, contradicting differential privacy. Combining these two parts yields the lower bound of Theorem 1. We believe the techniques developed in this proof introduce several ideas that may find further applications in lower bound proofs for differential privacy. We give a detailed presentation of our main ideas in Section 3 before proceeding to the formal proof in Section 4.

2

Related Work

Private Continual Counting. Private continual counting was introduced independently by [DNPR10] and [CSS10], who proposed the binary tree mechanism and established the foundations of differentially private computation under continual observation. While the original analysis achieves ℓ∞ error Oε,δ (log5/2 n) for pure DP and Oε,δ (log2 n) for approximate DP, a more careful analysis of the same algorithm yields improved bounds of Oε,δ (log2 n) and Oε,δ (log3/2 n) [JRSS23] respectively. [Hon15] and [APT24] proposed variants of tree mechanisms achieving better error in terms of the constant factors compared to the standard binary tree mechanism for the offline setting and the pure DP continual setting respectively. Since the binary tree mechanism is a special case of matrix factorization mechanisms, other approaches to improving the error include finding alternative matrix factorizations [FHU23, HUU23]. The best previously known lower bounds were obtained via packing arguments or by lower bounding the error of matrix factorization mechanisms [DNPR10, HUU23]. Our work complements this line of research by proving a matching lower bound for approximate DP, resolving the question of whether the binary tree mechanism is asymptotically optimal for ℓ∞ error. The Sparse Case. A natural variant of private continual counting assumes that the total number of events (number of 1’s in x) is bounded by ne ≪ n. In this sparse setting, [DNRR15] gave an upper bound of Oε,δ (min{log n + log2 ne , ne }), which can significantly improve over the binary tree mechanism when ne is small. [CLN+ 24] proved a lower bound of Ωε,δ (min{log n, ne }), showing that this improvement is tight. In our setting, we do not assume a bound on ne , so the results apply with ne ≤ n, recovering the suboptimal Oε,δ (log2 n) upper bound and Ωε,δ (log n) lower bound. Applications. Private continual counting has found applications across a range of machine learning and optimization tasks. The work of [JKT12] was the first to use it for differentially private online learning via a follow-the-leader approach combined with the binary tree mechanism. Subsequent works extended this to the full-information and bandit setting [TS13, AS17]. These techniques were applied to federated learning [KMS+ 21], enabling practical private deep learning without sampling or shuffling. More recently, [CDP+ 24] showed that DP-FTRL, a correlated noise mechanism based on continual counting, provably outperforms DPSGD for differentially private learning. In the context of private stochastic convex optimization, variations of the binary tree mechanism have been used to extend the Frank Wolfe algorithm to differential privacy [AFKT21, HLL+ 22]. In all these applications, improving the accuracy of continual counting translates to improved accuracy in the downstream task. Related Continual Observation Problems. Several other problems in the continual observation model are closely related to private continual counting. The problem of privately counting distinct elements in

4

the case where items can be both inserted and deleted was studied by [JKR+ 23, HSS24, CEM+ 25], where continual counting on a difference stream serves as a subroutine. [HUU24] studied continual decaying sums, a generalization of continual counting where older observations are down-weighted over time. Continual counting with privacy expiration, where the privacy guarantee degrades gracefully over time, was studied by [AHP+ 24]. Graph problems under continual observation, including triangle counting and other graph statistics, were studied by [FHO21, RS25], with continual counting appearing as a key subroutine in several of these results.

3

Proof Overview and Main Ideas

In this section, we present the high level ideas and overall structure of our lower bound proof for private continual counting. Along the way, we present the intuition behind each step and explain the barriers we overcome. Throughout, we assume that the mechanism M is oblivious, i.e. M(x) = Ax + z for a noise vector z independent of x (see Section 4 for the justification). Bounding Noise via Linear Measurements. In order to best motivate our approach to lower bounding the noise E[∥z∥∞ ], let us start by sketching an approach for lower bounding E[∥z∥22 ], and then argue how we adapt it to a local notion of noise we call residual noise, which will ultimately yield a lower bound on E[∥z∥∞ ]. Fix a coordinate i ∈ [n]. If M(x) = Ax + z is (ε, δ)-DP for small enough constants ε, δ > 0, then it must be the case that for any neighboring pair of inputs x′ , x′′ ∈ {0, 1}n that differ in the i’th input bit, if x is chosen uniformly among {x′ , x′′ }, then it is not possible for an adversary to guess x from M(x) = Ax + z with high probability. Importantly, this must be the case even when given knowledge of the pair x′ , x′′ . Since x′ , x′′ differ only in the i’th input bit, the adversary just needs to guess the value of xi . Without loss of generality we consider that x′i = 0 and x′′i = 1, whereas x′j = x′′j for all j ̸= i. Let x be uniform in {x′ , x′′ }. We consider an adversary that estimates xi in the following way. They first compute Ax′ and subtract it from M(x) to obtain Ax − Ax′ + z = xi Aei + z. The idea is now to define a linear measurement ψ i ∈ Rn for i (that is, a vector defining a linear form y → ⟨ψ i , y⟩ applied to a vector y ∈ Rn ), and let the adversary compute the estimate x̂i =

⟨ψ i , z⟩ ⟨ψ i , xi Aei + z⟩ = xi + i . i ⟨ψ , Aei ⟩ ⟨ψ , Aei ⟩

Since x̂i is a function of M(x) − Ax′ , it is (ε, δ)-differentially private by the postprocessing property of differential privacy. We can apply the following lemma to x̂i because it is an estimate of the binary variable xi with additive noise ⟨ψ i , z⟩/⟨ψ i , Aei ⟩. Lemma 1 ([GV16]). Any (ε, δ)-DP mechanism M releasing a private binary variable x ∈ {0, 1} as M(x) = x + z for a noise variable z independent of x must have E[z2 ] = Ω(min{ε−2 , δ −2 }). We conclude that the error of the adversary is E[⟨ψ i , z⟩2 ] = Ω(min{ε−2 , δ −2 }). ⟨ψ i , Aei ⟩2 Intuitively, this says that the noise z, when measured in the direction of ψ i , must be large relative to the signal ⟨ψ i , Aei ⟩. Otherwise, the adversary could distinguish xi = 0 from xi = 1, violating privacy. Overall, it implies that for all i ∈ [n], E[⟨ψ i , z⟩2 ] = Ω(⟨ψ i , Aei ⟩2 min{ε−2 , δ −2 }). The idea isPnow to carefully choose the linear measurements ψ i as orthogonal and unit length. In this way, we have i E[⟨ψ i , z⟩2 ] ≤ E[∥z∥22 ]. Therefore, ! X X 2 i 2 i 2 −2 −2 E[⟨ψ , z⟩ ] = Ω ⟨ψ , Aei ⟩ · min{ε , δ } . E[∥z∥2 ] ≥ i

i

5

Variations of this idea can be used to prove the known E[∥z∥22 ] = Ω(n log2 n) lower bound by choosing ψ i = U V t ei where A = U ΣV t is the singular value decomposition of A. Unfortunately, this only yields a lower bound of Ω(log2 n) on E[∥z∥2∞ ]. Tree Basis. Inspired by the approach just outlined, we next attempt to adapt these ideas to lower bounding E[∥z∥∞ ]. The main barrier is that if an adversary again computes xi Aei + z and takes linear measurements ψ i , then we inevitably lower bound E[∥z∥22 ]. Our first task is thus to find a different decomposition of the mechanism output so that the adversary can instead compute vectors of the form xi ν i + q, where P q is a noise vector whose entries reflect a local rather than global contribution of z, and ν i is chosen so that i ⟨ψ i , ν i ⟩2 is large, for some linear measurements ψ i . Recall that the proof has two main parts. We now describe the first: rewriting the noise in a basis more closely resembling the binary tree mechanism, which converts the task of lower bounding E[∥z∥∞ ] into lower bounding a weighted sum of residual noise contributions. The basis is constructed as follows. Assuming for simplicity that n is a power of two, consider a perfect binary tree T of height h = log2 n, i.e. T has n leaves. We think of the n leaves as being associated with the coordinates of Ax + z so that the i-th leaf corresponds to (Ax + z)i . We now define a set of vectors from T that together form a basis for Rn . For every node u ∈ T that is either the root or the right child of its parent, we define a vector χu which is the indicator vector of the leaves in the subtree rooted at u. There are exactly n such vectors, and they form a basis of Rn (though not an orthonormal basis). See Figure 1 for an example of the tree basis for n = 8 leaves. χ1-8 11111111 d=0

χ5-8 00001111 d=1

χ3-4

χ7-8

00110000

00000011

d=2

χ2

χ4

χ6

χ8

01000000

00010000

00000100

00000001

d=3

1

2

3

4

5

6

7

8

leaf index i

root or right child (χu defined) left child (no χu )

Figure 1: Binary tree basis for n = 8. Filled nodes are the root or right children and have a χu vector defined, shown with its binary indicator string. Empty nodes are left children and have no χu vector. For clarity, each vector χu in this figure uses the range of leaves in the subtree rooted at u to denote u, e.g. the root has χ1−8 . The depth of the tree level is denoted by d. The reason for using this basis is that every suffix vector Aei has a simple representation in it. More precisely, if Aei is the vector with ones in positions j ≥ i and zeros elsewhere, then X Aei = χu u∈I(i)

for the set I(i) of nodes that are right children of the path to the i’th leaf from the root (we refer the reader to Section 4 for the precise statement). Letting V(T ) ⊂ T be the set of nodes u with a χu vector defined

6

(right children and the root), we see that for every input x, we may write X X au χu , xi . Ax = au = u∈V(T )

i:u∈I(i)

Similarly, since the χu vectors form a basis, the noise vector also has a unique expansion X z= bu χu . u∈V(T )

For a leaf i, the released noise in coordinate i is therefore the sum of the coefficients bu over the nodes u on the root-to-leaf path to i for which χu is defined: X zi = bu , u∈Anc(i)∩V(T )

where Anc(i) are the ancestors of the i’th leaf (including the i’th leaf). Thus the ℓ∞ error is controlled by these path sums. Noise Accumulation. Having established the tree basis, we now turn to the second part of the proof: constructing the adversary. To define the vectors ν i and q, we need to understand how the noise z is distributed across the tree. Specifically, we argue that noise accumulates up the tree when it has “residual uncertainties”, a notion we now formalize. Consider a node u ∈ T , let T u be the subtree rooted at u, and let V(T u ) = T u ∩ V(T ) be the set of nodes v in T u with a χv vector defined. We now consider the accumulation of the noise zi up to node u defined as X z<u := bv . i v∈(V(T u )\{u})∩Anc(i)

Thus z<u gives the contribution to zi from nodes below u. Our next key idea is to lower bound E[maxi zi − i mini zi ] rather than E[∥z∥∞ ] directly, avoiding working with absolute values. This is sufficient since ∥z∥∞ ≥ (maxi zi − mini zi )/2. If L(T u ) denotes the indices of the leaves of T u , we may now consider max<u (z) := maxu z<u i i∈L(T )

and min<u (z) :=

min z<u i .

i∈L(T u )

Our main inductive argument is to show that E[max<u (z) − min<u (z)] increases as we move up the tree towards the root. Finally, for the root ρ, we have max<ρ (z) − min<ρ (z) = (max zi − bρ ) − (min zi − bρ ) = max zi − min zi , i

<ρ

i

i

i

<ρ

and thus a lower bound on E[max (z) − min (z)] directly translates to a lower bound on E[∥z∥∞ ]. Consider now a non-leaf node u and the range max<u (z) − min<u (z). Let ℓ(u) denote the left child of u and r(u) the right child. We see that max<u (z) − min<u (z) = max{max<ℓ(u) (z), max<r(u) (z) + br(u) } − min{min<ℓ(u) (z), min<r(u) (z) + br(u) }. This holds since every i ∈ T r(u) has r(u) as an ancestor (only the right child of u has a χ-vector). Using that max{a, b} − min{c, d} = (a − c)/2 + (b − d)/2 + |a − b|/2 + |c − d|/2 we get max<u (z) − min<u (z) =

max<ℓ(u) (z) − min<ℓ(u) (z) max<r(u) (z) − min<r(u) (z) + 2 2 <ℓ(u)

+

min max<ℓ(u) (z) − max<r(u) (z) − br(u) + 2 7

(z) − min<r(u) (z) − br(u) 2

. (1)

The first line is very convenient as it expresses max<u (z) − min<u (z) recursively as the average of the same quantity in the two children’s subtrees. What remains is thus to argue that the second line introduces a noticeable growth in max<u (z) − min<u (z) as we move up the tree. Taking expectation on both sides of (1), we thus need to lower bound i h (2) E max<ℓ(u) (z) − max<r(u) (z) − br(u) , and symmetrically for min. Here our main observation is that max<ℓ(u) (z) and max<r(u) (z) depend only on the noise below ℓ(u) and r(u). We thus define a type of “residual noise”. Let ∆<u (z) denote the random variable giving the noise bv for every v in the subtree below u (excluding u). We now define σu to capture how well br(u) can be predicted from the noise ∆<ℓ(u) (z), ∆<r(u) (z): σu (∆<ℓ(u) (z), ∆<r(u) (z)) := inf E[|br(u) − m| | ∆<ℓ(u) (z), ∆<r(u) (z)]. m

Returning to (2) and recalling that max we thus conclude that (2) is at least

<ℓ(u)

(z) and max<r(u) (z) depend only on ∆<ℓ(u) (z), ∆<r(u) (z)

σu := E[σu (∆<ℓ(u) (z), ∆<r(u) (z))]. We thus get an increase in E[max<u (z) − min<u (z)] if there is still randomness left in br(u) conditioned on the noise in the subtrees below ℓ(u) and r(u). In particular, recursively unfolding (1) and letting d(u) denote the depth of a node u ∈ T with the root ρ at depth 0, we get E[∥z∥∞ ] ≥ E[max zi − min zi ]/2 i

i

= E[max<ρ (z) − min<ρ (z)]/2 h

≥

1X 4

X

2−d σu .

(3)

d=0 u∈T :d(u)=d

Ph P Observe that d=0 u∈T :d(u)=d 2−d σu equals the expected sum of σu values along a uniform random rootto-leaf path in T . Before proceeding to explain how we lower bound this sum of σu values, let us compare to the classic binary tree mechanism upper bound. There, every node in the binary tree adds independent noise of variance Θ(log n). This means that even conditioned on the √ noise in the subtrees√below ℓ(u) and r(u), we still have E[inf m E[|br(u) − m| | ∆<ℓ(u) (z), ∆<r(u) (z)]] = Ω( log n). Summing Ω( log n) for each of the log2 n nodes along a root-to-leaf path leads to the claimed Ω(log3/2 n) lower bound. By (3), our goal reduces to showing that no private mechanism can make do with small residual noise σu . Obstacles for Bounding Residual Noise via Linear Measurements. The main obstacle is that the adversary cannot directly compute the subtree noise ∆<ℓ(u) (z), ∆<r(u) (z) needed to predict br(u) . To see why, consider the following attempt: let the adversary compute xi Aei + z, write it (uniquely) in the basis χu and thereby obtain, for every node u ∈ V(T ), the value bu + xi 1{u ∈ I(i)}. Next, for every non-leaf node u ∈ T , if the adversary could compute ∆<ℓ(u) (z), ∆<r(u) (z), they could subtract the conditional median mu (∆<ℓ(u) (z), ∆<r(u) (z)), the smallest minimizer of E[|br(u) −m| | ∆<ℓ(u) (z), ∆<r(u) (z)] over m, from br(u) +xi 1{r(u) ∈ I(i)}, obtaining a residual qu := br(u) −mu (∆<ℓ(u) (z), ∆<r(u) (z)) satisfying E[|qu |] = σu (see Figure 2 for an illustration). This would produce the desired vector xi ν i + q, where both ν i and q are indexed over non-leaf nodes u ∈ T , with ν i having entries 1{r(u) ∈ I(i)}. Unfortunately the adversary cannot compute ∆<ℓ(u) (z), ∆<r(u) (z) from xi Aei + z. The obstacle is that for any node v ∈ I(i) in the subtrees below ℓ(u) or r(u), the adversary observes bv + xi rather than bv alone. Since xi is unknown, the adversary cannot extract the noise bv . To remedy this, we take a step back and slightly redefine σu . 8

u

ℓ(u)

r(u)

br(u) + xi · 1{r(u) ∈ I(i)}

subtract mu ∆<ℓ(u) , ∆<r(u) ⇒ residual noise σu

∆<ℓ(u) (z)

∆<r(u) (z)

Figure 2: Adversary at node u ∈ T (which may or may not be in V(T )): given the noise ∆<ℓ(u) (z) and ∆<r(u) (z) in the two subtrees, the adversary computes mu and subtracts it from br(u) + xi · 1{r(u) ∈ I(i)} to obtain a residual σu . Noise Prediction via Grandchildren. Consider again a non-leaf node u and assume the children of u are also internal nodes. Instead of arguing that max<u (z) − min<u (z) grows compared to (max<ℓ(u) (z) − min<ℓ(u) (z))/2 + (max<r(u) (z) − min<r(u) (z))/2, we can also relate it to the grandchildren. In more detail, consider first the two grandchildren ℓ(ℓ(u)) and ℓ(r(u)) who are both left children of their parent. Since Anc(i) for i ∈ L(T ℓ(ℓ(u)) ) contains none of r(u), r(ℓ(u)) and r(r(u)) (the only nodes among u, <ℓ(ℓ(u)) the children of u, and the grandchildren, who have a χ-vector), we get z<u = zi . Likewise, Anc(i) for i ℓ(r(u)) i ∈ L(T ) contains precisely r(u) and hence, similarly to (1), we get max<u (z) − min<u (z) ≥ max<ℓ(ℓ(u)) (z) − min<ℓ(ℓ(u)) (z) max<ℓ(r(u)) (z) − min<ℓ(r(u)) (z) + + 2 2 min max<ℓ(ℓ(u)) (z) − max<ℓ(r(u)) (z) − br(u) + 2

<ℓ(ℓ(u))

(z) − min<ℓ(r(u)) (z) − br(u) .

2

(4)

We can thus define σu,ℓ to measure the residual noise in br(u) conditioned on the grandchildren ℓ(ℓ(u)) and ℓ(r(u)) (see Figure 3): σu,ℓ := E[inf E[|br(u) − m| | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)]]. m

The symmetric case where we consider the grandchildren r(ℓ(u)) and r(r(u)) is slightly more complicated as Anc(i) for i ∈ L(T r(ℓ(u)) ) contains r(ℓ(u)) and for i ∈ L(T r(r(u)) ) contains both r(u) and r(r(u)). This gives max<u (z) − min<u (z) ≥ max<r(ℓ(u)) (z) − min<r(ℓ(u)) (z) max<r(r(u)) (z) − min<r(r(u)) (z) + + 2 2 max<r(ℓ(u)) (z) − max<r(r(u)) (z) + br(ℓ(u)) − br(u) − br(r(u)) + 2 min<r(ℓ(u)) (z) − min<r(r(u)) (z) + br(ℓ(u)) − br(u) − br(r(u)) .

2

(5)

We handle this by measuring the residual noise in the sum br(ℓ(u)) − br(u) − br(r(u)) instead (see Figure 4): σu,r := E[inf E[|br(ℓ(u)) − br(u) − br(r(u)) − m| | ∆<r(ℓ(u)) (z), ∆<r(r(u)) (z)]]. m

9

u

ℓ(u)

r(u)

predict br(u) with residual noise σu,ℓ

ℓ(ℓ(u))

r(ℓ(u))

ℓ(r(u))

r(r(u))

∆<ℓ(ℓ(u)) (z)

∆<r(ℓ(u)) (z)

∆<ℓ(r(u)) (z)

∆<r(r(u)) (z)

known

unknown

known

unknown

Figure 3: Case ℓ at a node u of even depth: given the noise ∆<ℓ(ℓ(u)) (z) and ∆<ℓ(r(u)) (z) in the two left grandchildren’s subtrees (solid), the adversary predicts br(u) with residual noise σu,ℓ . The right grandchildren’s subtrees (dashed) need not be known. Averaging (4) and (5), we conclude X

E[max<u (z) − min<u (z)] ≥ σu,ℓ /2 + σu,r /2 +

f,g∈{ℓ,r}

h i E max<f (g(u)) (z) − min<f (g(u)) (z) 4

.

Starting from the root, which has depth 0, we can recursively unfold this sum and, similarly to (3), we conclude   h/2 X X E[∥z∥∞ ] = Ω  2−2d (σu,ℓ + σu,r ) . (6) d=0 u∈T :d(u)=2d

Note that the sum is again the expectation over a random root-to-leaf path, of the sum of σu,ℓ and σu,r for nodes u at even levels of T . Now, let us look carefully at what we have gained from predicting the noise from the grandchildren. The key observation is that for an adversary trying to distinguish neighboring x′ , x′′ with x′i ̸= x′′i , it holds for any node u that if i ∈ L(T r(ℓ(u)) ) ∪ L(T r(r(u)) ), then v ∈ / I(i) for all v ∈ T ℓ(ℓ(u)) \ {ℓ(ℓ(u))} and all ℓ(r(u)) v ∈T \ {ℓ(r(u))}. The symmetric thing holds for i ∈ L(T ℓ(ℓ(u)) ) ∪ L(T ℓ(r(u)) ). In a nutshell, if an adversary “attacks” a variable xi with i in the subtree of one of the two grandchildren r(ℓ(u)) and r(r(u)), then the adversary can directly compute ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z) and predict br(u) up to an expected absolute error of σu,ℓ . A symmetric argument allows the adversary to predict br(ℓ(u)) − br(u) − br(r(u)) up to expected error σu,r if i is in the subtree of either ℓ(ℓ(u)) or ℓ(r(u)). Let us ignore this slightly more tedious case in the proof overview. Unfortunately, a new obstacle arises from this approach. One central idea in the linear Pmeasurements approach for bounding the noise, is to define orthogonal unit length vectors ψ i so that i E[⟨ψ i , z⟩2 ] ≤ E[∥z∥22 ]. Now, if we follow the outlined approach and use the noise in the pair of grandchildren not containing the i’th leaf, then the distribution of the residual noise vector q depends on i. That is, if i falls in one of the subtrees rooted at the grandchildren ℓ(ℓ(u)), ℓ(r(u)), we get one distribution, and if it falls in the subtrees rooted at r(ℓ(u)), we get another. If we have different residual noise vectors qi for different i, then P r(r(u)), i i 2 the argument i E[⟨ψ , q ⟩ ] ≤ E[∥q∥22 ] breaks, since q is not a fixed vector as it depends on i. Restricting to a Subtree. Our next idea is to restrict attention to a collection of leaf indices i that all result in the same noise predictions across the tree T . In more detail, consider a string s ∈ {ℓ, r}h/2 and 10

u

ℓ(u)

r(u)

predict br(ℓ(u)) − br(u) − br(r(u)) with residual noise σu,r

ℓ(ℓ(u))

r(ℓ(u))

ℓ(r(u))

r(r(u))

∆<ℓ(ℓ(u)) (z)

∆<r(ℓ(u)) (z)

∆<ℓ(r(u)) (z)

∆<r(r(u)) (z)

unknown

known

unknown

known

Figure 4: Case r at a node u of even depth: given the noise ∆<r(ℓ(u)) (z) and ∆<r(r(u)) (z) in the two right grandchildren’s subtrees (solid), the adversary predicts br(ℓ(u)) − br(u) − br(r(u)) with residual noise σu,r . The left grandchildren’s subtrees (dashed) need not be known. let T s be the subset of T defined as follows. Starting from the root, from a node at an even depth 2d we descend into both children, and from a node at an odd depth 2d − 1 we descend only to the left child if sd = ℓ and only to the right child if sd = r. Let L(T s ) be the indices of the leaves of T s . The critical observation is that if u ∈ T s is a node of even depth 2d, then every i ∈ L(T s ) ∩ L(T u ) falls in one of the two subtrees T sd+1 (ℓ(u)) and T sd+1 (r(u)) . This implies that an adversary trying to infer d+1 (ℓ(u)) d+1 (r(u)) xi via a linear measurement can compute ∆<sg (z), ∆<sg (z) regardless of which i ∈ L(T s ) the adversary attacks, where ℓe = r and re = ℓ denotes the opposite direction. The adversary can thus predict br(u) up to expected absolute error σu,ℓ if sd+1 = r, and predict br(ℓ(u)) − br(u) − br(r(u)) up to error σu,r if sd+1 = ℓ. Assume for simplicity that s = rr · · · r is the all-r string, so we do not have to deal with the br(ℓ(u)) − br(u) − br(r(u)) case. For a neighboring pair x′ , x′′ with x′i ̸= x′′i and x uniform in {x′ , x′′ }, an adversary can now compute br(u) + xi 1{r(u) ∈ I(i)} − muℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)) = qu + xi 1{r(u) ∈ I(i)} for every u ∈ T s of even depth, where E[|qu |] = σu,ℓ . Here muℓ is a conditional median of br(u) . Letting ν i be the vector with entries 1{r(u) ∈ I(i)} for every u ∈ T s of even depth, the adversary has thus obtained a vector xi ν i + q with E[|qu |] = σu,ℓ . Moreover, if we draw s uniformly in {ℓ, r}h/2 , then a uniform random root-to-leaf path in T s , is uniform random in T . Thus if we can lower bound the expected sum of σu,ℓ + σu,r along a uniform random root-to-leaf path in every T s , then we get the same lower bound on (6). We thus fix an arbitrary s ∈ {ℓ, r}h/2 and lower bound h/2 X

X

2−d σu,sg . d+1

(7)

d=0 u∈T s :d(u)=2d

For simplicity of the proof overview, let us merely consider s = rr · · · r and See Figure 5 for an example for n = 16 and s = rr.

Ph/2 P d=0

−d σu,ℓ . u∈T s :d(u)=2d 2

Median-of-Three Trick. We now have an adversary for every i ∈ L(T s ) that can compute xi ν i + q. Returning to the strategy of using linear P measurements, the natural next step would be to define orthogonal unit length vectors ψ i for which i ⟨ψ i , ν i ⟩2 is large. By orthogonality, we would simultaneously get 11

d=0

d=1

d=2

d=3

d=4

1

2

3

4

5

6

7

8 9 leaf index i

10

11

12

13

14

15

16

node in T s ∩ V(T ) node in T s \ V(T ) node not in T s

Figure 5: The subtree T s for s = rr in a binary tree of height h = 4. Nodes in T s ∩ V(T ) are filled black, nodes in T s \ V(T ) have a solid white border, and nodes not in T s have a dashed border. For each node u ∈ T s at even depth (d = 0 and d = 2), both children of u are included in T s . For each node u at odd depth (d = 1 and d = 3), only the right child of u is included. The highlighted leaves give L(T s ) = {6, 8, 14, 16}. i 2 2 i E[⟨ψ , q⟩ ] ≤ E[∥q∥2 ] =

2 u∈T s :d(u) even E[qu ]. Unfortunately, our guarantee E[|qu |] = σu,ℓ is not suffi2 cient to give any upper bound on E[qu ] and thereby E[∥q∥22 ]. To overcome this, we use a trick from Larsen,

P

P

Pagh, Tetek [LPT21]. An immediate corollary of their work is the following. Corollary 1 ([LPT21]). Let Z1 , Z2 , Z3 be i.i.d. real-valued random variables. Then E[median{Z1 , Z2 , Z3 }2 ] ≤ 3 · E[|Z1 |]2 . Now using the composition property of differential privacy, we have that the mechanism M′ releasing (Ax + z(1) , Ax + z(2) , Ax + z(3) ) for three i.i.d. draws of the noise z of the mechanism M is (3ε, 3δ)-DP. Thus even if we give an adversary access to three independent copies of the noise, privacy still guarantees that one cannot distinguish x′ , x′′ . Crucially, the adversary trying to infer xi can now compute, for every u ∈ T s of even depth, the value (2) (3) median{xi 1{r(u) ∈ I(i)} + q(1) u , xi 1{r(u) ∈ I(i)} + qu , xi 1{r(u) ∈ I(i)} + qu } = (2) (3) xi 1{r(u) ∈ I(i)} + median{q(1) u , qu , qu }.

From Corollary 1, this results in a vector xi ν i + q where (2) (3) 2 (1) 2 2 E[(qu )2 ] = E[median{q(1) u , qu , qu } ] ≤ 3E[|qu |] = 3σu,ℓ .

We thus have E[∥q∥22 ] ≤ 3

h/2 X

X

2 σu,ℓ .

(8)

d=0 u∈T s :d(u)=2d

As suggested earlier, next step is to define the linear measurements ψ i and then use privacy to argue P the 2 i 2 that E[∥q∥2 ] = Ω( i ⟨ψ , ν i ⟩2 ). Indeed this would lower bound the sum of σu,ℓ . Sadly, this is not enough as we need to bound the weighted sum of σu,ℓ given in (7). We thus have a mismatch, both in terms of weights, but more critically, (8) is a sum of squares whereas (7) is a sum. 12

Let us mention that our full proof handles the above in a slightly different manner. Rather than attacking different xi variables directly, we separate the noise reduction step from the linear measurement attacks, c that is (3ε, 3δ)-DP when making the proof more modular. In essence, we define a derived mechanism M s c Since restricted to / L(T ), and apply the linear measurements argument to M. √ inputs with xi = 0 for i ∈ s |L(T )| = n and the lower bound is polylogarithmic, the restriction to a smaller input domain is harmless. From Weighted Sum to Max Bound. We now address the mismatch between the sum of squares in (8) and the weighted sum (7) that we need to lower bound. We will show√that for at least half of the h/2 choices of depth 2d, at least half of the nodes u ∈ T s must have σu,ℓ = Ω( log n). This still lower bounds (7) by the desired Ω(log3/2 n). The way we approach it is as follows: for every even depth 2d, consider the median md :=

median

u∈T s :d(u)=2d

{σu,ℓ }.

Now let J ⊆ {0, . . . , h/2 − 1} with |J | = h/4 be so that the medians md with d ∈ J are the h/4 smallest of the h/2 medians. Furthermore, for every d ∈ J , let Jd consist of the nodes u ∈ T s of depth 2d having the smallest σu,ℓ values. In particular, each such σu,ℓ satisfies σu,ℓ ≤ md . Let us now define σ := max max σu,ℓ . d∈J u∈Jd

Then by definition of J , for each of the h/4 values of d not in J , we have md ≥ σ. Hence, at least half the nodes of depth 2d have σu,ℓ ≥ σ. Summing across the h/4 depths not in J , we lower bound (7) by h/2 X

X

d=0 u∈T s :d(u)=2d

2−d σu,ℓ ≥

X

X

d∈J / u∈T s :d(u)=2d∧σ

2−d md ≥ u,ℓ ≥md

X d∈J /

2d−1 2−d σ =

X

σ/2 = hσ/8.

(9)

d∈J /

With this in mind, we now set out to prove that for any choice of J ⊆ {0, . . . , h/2 − 1} with |J | = h/4 and any choice of {Jd }d∈J √ with Jd containing half the nodes in T s of depth 2d, there is at least one node u ∈ ∪d∈J Jd with σu,ℓ = Ω( log n). What we have achieved is that we now need to handle the simpler task of showing that just one residual noise must be large, rather than showing that an intricate weighted sum is large. Furthermore, showing that just one σu,ℓ is large is also possible when given a lower bound on the sum of squared values, as in (8), making the attacks via linear measurements amenable. Privacy Attacks via Linear Measurements. We now describe the second part of the proof: constructing the adversary using linear measurements. Having analyzed the noise structure in the tree, we have shown that the noise of mechanism M has residual contributions σu,ℓ along the tree. It remains to show that if these residual contributions are small, then privacy is violated. Recall that for simplicity we consider s = rr . . . r and an adversary trying to distinguish neighboring inputs x′ , x′′ with x′i ̸= x′′i for some i ∈ L(T s ). As shown above, this adversary can compute a vector xi ν i + q with an entry for each non-leaf u ∈ T s of even depth 2 so that E[q2u ] ≤ 3σu,ℓ and νui = 1{r(u) ∈ I(i)}. We now show that if the σu,ℓ are small, the adversary can use linear measurements to distinguish x′ from x′′ , contradicting privacy. Recall from above the arbitrary sets J ⊆ {0, . . . , h/2−1} with |J | = h/4 and {Jd }d∈J with Jd containing half the nodes in T s of depth 2d. We need to define ψ i (specified shortly) with the goal of showing that at least one σu,ℓ for u ∈ ∪d∈J Jd is large. Since post-processing preserves privacy, the adversary may set all coordinates corresponding to u ∈ / ∪d∈J Jd to 0, obtaining a shorter vector. It now suffices to show that 2 implies that σu,ℓ is large. Let E[q2u ] is large for at least one remaining coordinate u, which by E[q2u ] ≤ 3σu,ℓ P P 2 2 σ = maxd∈J maxu∈Jd σu,ℓ . Then by definition, E[∥q∥2 ] ≤ d∈J u∈Jd 3σ . Since T s has 2d nodes at even depth 2d and Jd contains half of them, we have |Jd | = 2d−1 , meaning deeper levels contribute more to the sum. To balance this across depths, the adversary scales each coordinate of xi ν i + q by 2−d/2 for nodes u 13

at even depth 2d. Let r be the resulting noise vector with ru = 2−d/2 qu for u ∈ ∪d∈J Jd and let µi be the vector with coordinates µiu = 2−d/2 νui . The adversary has thus computed the vector xi µi + r. With ψ i as the linear measurement for leaf index i, the adversary computes the estimate x̂i =

⟨ψ i , xi µi + r⟩ ⟨ψ i , r⟩ = x + . i ⟨ψ i , µi ⟩ ⟨ψ i , µi ⟩

Since x̂i is a private estimate of the binary variable xi , applying Lemma 1 the error of the adversary for coordinate i is E[⟨ψ i , r⟩2 ] = Ω(min{ε−2 , δ −2 }). ⟨ψ i , µi ⟩2 P If we choose orthogonal unit length vectors ψ i for i ∈ L(T s ), then i∈L(T s ) E[⟨ψ i , r⟩2 ] ≤ E[∥r∥22 ] and E[∥r∥22 ] =

X X

E[r2u ] =

d∈J u∈Jd

≤

X X

X X

2−d E[q2u ]

d∈J u∈Jd −d

2

2

3σ = O(hσ 2 )

d∈J u∈Jd

P since d∈J |Jd | · 2−d = |J |/2 = h/8. P The final step of the proof is now to choose appropriate vectors ψ i so that i ⟨ψ i , µi ⟩2 is large. The choice of ψ i is inspired by the Haar wavelet basis. Given a perfect binary tree over n leaves, the Haar wavelet basis has a vector hu for each internal node u ∈ T . If the subtree rooted at u has nu leaves, then the vector √ √ for leaves hu has coordinates −1/ nu for leaves in the subtree rooted at ℓ(u) and it has coordinates 1/ nu √ in the subtree rooted at r(u). Finally, the basis also contains the vector with all coordinates 1/ n. The Haar wavelet basis is an orthonormal basis of Rn . If we now arrange the vectors hu as columns of a matrix H and compute its transpose H t , then the resulting matrix is also orthonormal. More precisely, we use as ψ i the columns of H t , where H is the matrix of the Haar wavelet basis restricted to T s . Concretely, we let ψ i be the vector with one coordinate for every u ∈ T s . For a node u of depth 2d, we / L(T u ), ψui = −2−(h/2−d)/2 if i ∈ L(T ℓ(u) ) and ψui = 2−(h/2−d)/2 if i ∈ L(T r(u) ). Since let ψui = 0 if i ∈ h/2−d 2 is the number of leaves in L(T s ) ∩ L(T u ), this P coincides with the transpose of the matrix H resulting from the Haar wavelet basis on T s . We expand i ⟨ψ i , µi ⟩2 and show that the sum is lower bounded by Ω(h2 ). P P i i 2 i 2 2 2 Combining the bound i E[⟨ψ , r⟩ ] = O(hσ ) from above with i ⟨ψ , µ ⟩ = Ω(h ), implies that 2 −2 −2 σ = Ω(h min{ε , δ }). Substituting into (9) finally gives us   !   h/2 3/2 3/2 X X h log n −d E[∥z∥∞ ] = Ω  2 σu,ℓ  = Ω(hσ) = Ω =Ω . max{ε, δ} max{ε, δ} s d=0 u∈T :d(u)=2d

4

Formal Lower Bound Proof

We restate our main result for convenience. Restatement of Theorem 1. For any 0 < ε < 1, 0 < δ < C for a sufficiently small constant C > 0, it holds that any (ε, δ)-DP mechanism M for continual counting has error ! log3/2 n max E[∥M(x) − Ax∥∞ ] = Ω , max{ε, δ} x∈{0,1}n where A is the n × n prefix-sum matrix.

14

We now prove Theorem 1. Our goal is to lower bound the noise needed to release a private version of Ax for a binary vector x ∈ {0, 1}n . By a reduction in prior works [BDKT12], we can assume that a mechanism Mo (x) releases Ax + z for a noise vector z independent of x. Concretely, an (ε, δ)-DP data dependent mechanism (M(x) may depend on x) can be made oblivious (Mo (x) = Ax + z for z independent of x) at the cost of scaling ε to 2ε and δ to eε δ. For the parameter range 0 < ε < 1, this is a constant scaling in the parameters and disappears in the Ω(·) notation. Essentially, if M is an (ε, δ)-DP mechanism with error maxx∈{0,1}n E[∥M(x) − Ax∥∞ ], then there exists an oblivious mechanism Mo that is (2ε, eδ)-DP with error max E[∥M(x) − Ax∥∞ ] ≥

x∈{0,1}n

max E[∥Mo (x) − Ax∥∞ ] = E[∥z∥∞ ].

x∈{0,1}n

(10)

Tree Structure. We assume n is a power of 16 and let h = log2 n. This only affects the lower bound by a constant factor as we can use the length 16⌊log16 n⌋ prefix of x to embed the hard instance. To define a basis for Rn , consider a binary tree T of height h, i.e. T has n leaves, where the i-th leaf corresponds to the i-th coordinate of Ax + z. Let V(T ) be the set of nodes that are either the root or the right child of their parent. We use the notation ℓ(u) to denote the left child and r(u) to denote the right child of a non-leaf node u. For each node u ∈ V(T ), we define χu as the indicator vector having a 1 in coordinates corresponding to the leaves in the subtree T u rooted at u and 0 elsewhere. We also define V(T u ) := V(T ) ∩ T u as the nodes v ∈ T u with χv defined. Ph We observe that the number of vectors |V(T )| = 1 + d=1 2d−1 = n. Furthermore, we claim that every suffix vector Aei ∈ Rn having a 1 in positions j ≥ i and 0 elsewhere can be written as a linear combination of the χu vectors. Since the suffix vectors span Rn , we conclude that the χu vectors span Rn . Moreover, since there are n of them, they form a basis (although neither orthogonal nor unit length). To write Aei as a linear combination of the χu vectors, initialize ŷ = 0 and traverse the path from the root to the i’th leaf. For each node u visited, if i is the left-most leaf in the subtree T u , add χu to ŷ r(u) and terminate. Otherwise, if u is an internal node and the path descends to ℓ(u), to ŷ. Upon P add χu termination, we have ŷ = Aei . Define I(i) ⊆ V(T ) as the nodes such that Aei = u∈I(i) χ . We observe that n n X X X X X Ax = xi Aei = xi χu = xi χu . i=1

i=1 u∈I(i)

u∈V(T ) i:u∈I(i)

Thus, if we define au :=

X

xi ,

i:u∈I(i)

P then Ax = u∈V(T ) au χu . We note that since the χu vectors form a basis, this linear combination is unique. P Since the χu vectors form a basis, there is also a unique linear combination so that z = u∈V(T ) bu χu with bu ∈ R. From this it also follows that X X zi = bu χui = bu . u∈V(T ):χu i =1

u∈V(T )

Note that the nodes u with χui = 1 are precisely Anc(i) ∩ V(T ), where Anc(i) is the set of all ancestors of the i’th leaf, P including the leaf itself. Thus, to lower bound ∥z∥∞ we need to show that there is an index i for which u∈Anc(i)∩V(T ) bu is large in absolute value. Noise Accumulation. We next argue that noise accumulates up the tree T in a subtle manner. First observe that ∥z∥∞ ≥ (maxi zi − mini zi )/2. We thus lower bound E[maxi zi − mini zi ] instead of directly lower bounding E[∥z∥∞ ], circumventing the absolute value. We do this inductively up the tree T . For any node u ∈ T , let T u be the subtree rooted at u and define L(T u ) as the indices of the leaves in the subtree rooted at u. For each i ∈ L(T u ), define X z<u := bv . i v∈(V(T u )\{u})∩Anc(i)

15

sums only the contributions to zi from nodes strictly below u on the path from the root to the That is, z<u i i’th leaf. Also define max<u (z) := maxu z<u i . i∈L(T )

and min<u (z) :=

min z<u i .

i∈L(T u )

We will show that max<u (z) − min<u (z) grows as we move up the tree. For any node u ∈ T , define ∆<u (z) as the random variable giving bv for every v ∈ V(T u ) \ {u}. That is, <u ∆ (z) gives the contributions to the noise vector z from χv vectors in the subtree rooted at u, excluding u itself. ∆<u (z) is thus a function of z, ∆<u (z) : V(T u ) \ {u} → R with ∆<u (z)(v) = bv for v ∈ V(T u ) \ {u}. We now consider how well br(u) can be predicted from the noise ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z) for u ∈ T that is not a leaf: i h σu,ℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)) := inf E br(u) − m | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z) . m

Also let σu,ℓ = E[σu,ℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z))]. For later use, we also define muℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)) as a measurable minimizer m of h i inf E br(u) − m | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z) , m

chosen as the smallest conditional median. Similarly, we also consider predicting the sum br(ℓ(u)) − br(u) − br(r(u)) from ∆<r(ℓ(u)) (z), ∆<r(r(u)) (z) for internal u ∈ T whose children are not leaves: i h σu,r (∆<r(ℓ(u)) (z), ∆<r(r(u)) (z)) := inf E br(ℓ(u)) − br(u) − br(r(u)) − m | ∆<r(ℓ(u)) (z), ∆<r(r(u)) (z) , m

and let σu,r = E[σu,r (∆<r(ℓ(u)) (z), ∆<r(r(u)) (z))]. Again, we also define mur (∆<r(ℓ(u)) (z), ∆<r(r(u)) (z)) as a measurable minimizer of i h inf E br(ℓ(u)) − br(u) − br(r(u)) − m | ∆<r(ℓ(u)) (z), ∆<r(r(u)) (z) , m

chosen as the smallest conditional median. Our goal is to show that max<u (z) − min<u (z) grows proportionally to σu,r and σu,ℓ . Intuitively, this means that if there is still randomness left in br(u) after revealing ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z), or in br(ℓ(u)) − br(u) − br(r(u)) after revealing ∆<r(ℓ(u)) (z), ∆<r(r(u)) (z), then the noise accumulates up the tree to create a large max<u (z) − min<u (z). This is captured in the following lemma Lemma 2. For any internal node u ∈ T whose children are not leaves, we have X E[max<u (z) − min<u (z)] ≥ σu,ℓ /2 + σu,r /2 + E[max<f (g(u)) (z) − min<f (g(u)) (z)]/4. f,g∈{ℓ,r}2

Proof. Let u be an internal node whose children are not leaves. We have max<u (z) − min<u (z) ≥ max{

max i∈L(T ℓ(ℓ(u)) )

z<u i ,

max i∈L(T ℓ(r(u)) )

z<u i } − min{

16

min i∈L(T ℓ(ℓ(u)) )

z<u i ,

min i∈L(T ℓ(r(u)) )

z<u i }.

Notice that max{a, b} = (a + b)/2 + |a − b|/2 and min{a, b} = (a + b)/2 − |a − b|/2 for any a, b. Hence max{a, b} − min{c, d} = (a + b)/2 − (c + d)/2 + |a − b|/2 + |c − d|/2 = (a − c)/2 + (b − d)/2 + |a − b|/2 + |c − d|/2. We now see that max i∈L(T ℓ(ℓ(u)) )

z<u − i

min i∈L(T ℓ(ℓ(u)) )

z<u = i

<ℓ(ℓ(u))

max i∈L(T ℓ(ℓ(u)) )

−

zi

min i∈L(T ℓ(ℓ(u)) )

<ℓ(ℓ(u))

zi

= max<ℓ(ℓ(u)) (z) − min<ℓ(ℓ(u)) (z). and max i∈L(T ℓ(r(u)) )

z<u − i

min i∈L(T ℓ(r(u)) )

z<u = i

<ℓ(r(u))

max i∈L(T ℓ(r(u)) )

zi

−

min i∈L(T ℓ(r(u)) )

<ℓ(r(u))

zi

= max<ℓ(r(u)) (z) − min<ℓ(r(u)) (z). Finally, we also have max i∈L(T ℓ(ℓ(u)) )

z<u − i

max i∈L(T ℓ(r(u)) )

<ℓ(ℓ(u))

max i∈L(T ℓ(ℓ(u)) )

zi

−

= z<u i <ℓ(r(u))

max i∈L(T ℓ(r(u)) )

zi

− br(u) =

max<ℓ(ℓ(u)) (z) − max<ℓ(r(u)) (z) − br(u) . and min i∈L(T ℓ(ℓ(u)) )

z<u − i

min i∈L(T ℓ(r(u)) )

= min<ℓ(ℓ(u)) (z) − min<ℓ(r(u)) (z) − br(u) . z<u i

We conclude max<u (z) − min<u (z) ≥ max<ℓ(ℓ(u)) (z) − min<ℓ(ℓ(u)) (z) max<ℓ(r(u)) (z) − min<ℓ(r(u)) (z) + + 2 2 min max<ℓ(ℓ(u)) (z) − max<ℓ(r(u)) (z) − br(u) + 2

<ℓ(ℓ(u))

(z) − min<ℓ(r(u)) (z) − br(u) 2

.

Now observe that max<ℓ(ℓ(u)) (z), max<ℓ(r(u)) (z), min<ℓ(ℓ(u)) (z) and min<ℓ(r(u)) (z) are all determined from ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z). Hence h i E max<ℓ(ℓ(u)) (z) − max<ℓ(r(u)) (z) − br(u) | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z) ≥ σu,ℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)) and h i E min<ℓ(ℓ(u)) (z) − min<ℓ(r(u)) (z) − br(u) | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z) ≥ σu,ℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)). Thus we have E[max<u (z) − min<u (z) | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)] ≥ E[max<ℓ(ℓ(u)) (z) − min<ℓ(ℓ(u)) (z) | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)] + 2 E[max<ℓ(r(u)) (z) − min<ℓ(r(u)) (z) | ∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)] + 2 σu,ℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)) σu,ℓ (∆<ℓ(ℓ(u)) (z), ∆<ℓ(r(u)) (z)) + . 2 2 17

By the law of total expectation, we conclude E[max<u (z) − min<u (z)] ≥ E[max<ℓ(ℓ(u)) (z) − min<ℓ(ℓ(u)) (z)] E[max<ℓ(r(u)) (z) − min<ℓ(r(u)) (z)] + + σu,ℓ . 2 2 Similarly for the grandchildren of u that are right children of their parents, namely r(ℓ(u)) and r(r(u)), we have max<u (z) − min<u (z) ≥ max{

max i∈L(T r(ℓ(u)) )

z<u i ,

max i∈L(T r(r(u)) )

z<u i } − min{

min i∈L(T r(ℓ(u)) )

z<u i ,

min i∈L(T r(r(u)) )

z<u i }.

Using the same formula for max{a, b} − min{c, d}, we notice that max i∈L(T r(ℓ(u)) )

− z<u i

max i∈L(T r(r(u)) )

<r(ℓ(u))

max i∈L(T r(ℓ(u)) )

zi

z<u = i

+ br(ℓ(u)) −

<r(r(u))

max i∈L(T r(r(u)) )

zi

− br(u) − br(r(u)) =

max<r(ℓ(u)) (z) − max<r(r(u)) (z) + br(ℓ(u)) − br(u) − br(r(u)) . and min i∈L(T r(ℓ(u)) )

z<u − i

min i∈L(T r(r(u)) )

= min<r(ℓ(u)) (z) − min<r(r(u)) (z) + br(ℓ(u)) − br(u) − br(r(u)) . z<u i

We notice that max<r(ℓ(u)) (z), max<r(r(u)) (z), min<r(ℓ(u)) (z) and min<r(r(u)) (z) are all determined from ∆<r(ℓ(u)) (z), ∆<r(r(u)) (z). Thus by the same arguments as above, we conclude E[max<u (z) − min<u (z)] ≥ E[max<r(ℓ(u)) (z) − min<r(ℓ(u)) (z)] E[max<r(r(u)) (z) − min<r(r(u)) (z)] + + σu,r . 2 2 By averaging, we finally conclude X E[max<u (z) − min<u (z)] ≥ σu,ℓ /2 + σu,r /2 + E[max<f (g(u)) (z) − min<f (g(u)) (z)]/4. f,g∈{ℓ,r}2

Recall that we assume n is a power of 16 and thus h = log2 n is even. If we say that the root ρ is at depth 0, then the leaves are at depth h. If we now recursively apply Lemma 2 on the even levels of T , starting from the root ρ and using that max<u (z) = min<u (z) = 0 when u is a leaf, we conclude h/2−1 <ρ

E[max

(z) − min

<ρ

(z)] ≥

X

X

2−2d−1 (σu,ℓ + σu,r ),

d=0 u∈T :d(u)=2d

where d(u) is the depth of u. Finally, observing that the root ρ satisfies ρ ∈ Anc(i) for all i we have E[∥z∥∞ ] ≥ E[maxi zi − mini zi ]/2 = E[max<ρ (z) + bρ − (min<ρ (z) + bρ )]/2 = E[max<ρ (z) − min<ρ (z)]/2 h/2−1

≥

X

X

2−2d−1 (σu,ℓ + σu,r ).

d=0 u∈T :d(u)=2d

18

We now rewrite this into an alternative, but more convenient representation. Let i be a uniform random leaf index. Then for a node u, we have Pr[u ∈ Anc(i)] = 2−d(u) . Letting pAnc(i) be the proper ancestors of the i’th leaf, i.e. Anc(i) but without the i’th leaf itself, we have h/2−1

E[∥z∥∞ ] ≥

X

X

Pr[u ∈ Anc(i)](σu,ℓ + σu,r )/2

d=0 u∈T :d(u)=2d h/2−1

=

X

X

E[1{u ∈ Anc(i)}](σu,ℓ + σu,r )/2

d=0 u∈T :d(u)=2d

 1 = · Ei∈L(T )  2

 X

σu,ℓ + σu,r  .

(11)

u∈pAnc(i):d(u)≡0 mod 2

What remains is thus to lower bound the expected sum of σu,ℓ and σu,r on the even levels of a uniformly random root-to-leaf path. Restricting to a Subtree. We now restrict attention to a subtree of T . Recall h is even, so there are h/2 odd depths 1, 3, . . . , h − 1. For a string s ∈ {ℓ, r}h/2 , let T s be the subset of T containing all nodes u for which the path from the root to u satisfies that in every odd depth 2j − 1, the path to u descends to the left child if sj = ℓ and to the right child if sj = r. For even levels, we allow descending into both children. Let L(T s ) be the indices in the leaves of T s . Now let s be uniform random in {ℓ, r}h/2 and let i be uniform random in L(T s ). Then the distribution of i is uniform among all leaves of T . By linearity of expectation, there must exist a choice of s ∈ {ℓ, r}h/2 such that   X 1 σu,ℓ + σu,r  E[∥z∥∞ ] ≥ · Ei∈L(T s )  2 u∈pAnc(i):d(u)≡0 mod 2

h/2−1

=

1 X · 2

X

Pr [u ∈ Anc(i)](σu,ℓ + σu,r )

d=0 u∈T s :d(u)=2d

i∈L(T s )

h/2−1

=

1 X · 2 d=0

X

2−d (σu,ℓ + σu,r ).

u∈T s :d(u)=2d

Fix such an s ∈ {ℓ, r}h/2 . For a character a ∈ {ℓ, r}, let ã denote the opposite character, i.e. ℓ̃ = r and r̃ = ℓ. Then, we further have h/2−1

E[∥z∥∞ ] ≥

1 X · 2

X

2−d · σu,sg . d+1

(12)

d=0 u∈T s :d(u)=2d

We will thus show that this sum is large for any s. From Weighted Sum to Max Bound. The bound in (12) requires us to bound a weighted sum of σu,sg values. We reduce this to the simpler case of merely showing that at least one term in the sum is d+1 large. More concretely, consider choosing J ⊆ {0, . . . , h/2 − 1} as a subset of h/4 out of the h/2 choices for d in the outer sum in (12). Next, for each d ∈ J with d > 0, choose a subset Jd of 2d−1 out of the 2d nodes u ∈ T s with d(u) = 2d. If d = 0 is in J , then that corresponds to the root and we choose J0 = {ρ}, which is the only node at depth 0. Assume we can show that for any such choice of J and {Jd }d∈J , we have max max σu,sg ≥ σ, d+1 d∈J u∈Jd

19

then we claim that E[∥z∥∞ ] ≥

hσ . 16

To see this, define for each d ∈ {0, . . . , h/2 − 1} the value md :=

median

u∈T s :d(u)=2d

{σu,sg }, d+1

where the median, for an even number of elements nd , is defined as the nd /2’th smallest element and for a set of size 1 is defined as the single element. Now let J ⊆ {0, . . . , h/2 − 1} be the indices d with the h/4 smallest values of md . For each d ∈ J , let Jd contain the 2d−1 nodes u ∈ T s with d(u) = 2d having the smallest values of σu,sg . By assumption, there is a d⋆ ∈ J and u ∈ Jd⋆ with σu,s^ ≥ σ. By definition d+1 d⋆ +1 ⋆ ⋆ of Jd , this implies md ≥ σ. By definition of J , it follows that for every d ∈ / J , we have md ≥ md⋆ ≥ σ. s Finally, for every d ∈ / J , it follows that at least half the nodes u ∈ T with d(u) = 2d have σu,sg ≥ σ. d+1 Since there are 2d nodes u in T s with d(u) = 2d, we conclude from (12) that h/2−1

1 X · 2

X

1 X ≥ · 2

X

E[∥z∥∞ ] ≥

2−d · σu,sg d+1

d=0 u∈T s :d(u)=2d

2−d · σu,sg d+1

d∈J / u∈T s :d(u)=2d

≥ =

1X 4

σ

d∈J /

hσ . 16

(13)

We can thus focus on showing that for any J ⊆ {0, . . . , h/2 − 1} with |J | = h/4 and any {Jd }d∈J , with Jd consisting of half the nodes of T s at depth 2d, there is at least one d ∈ J and one u ∈ Jd such that σu,sg d+1 is large. Noise Reduction. The first step in bounding σ = maxd∈J maxu∈Jd σu,sg for any choice of J and d+1 {Jd }d∈J , is to design an alternative mechanism whose noise is bounded in terms of σu,sg . d+1 h/2 c Consider an arbitrary s ∈ {ℓ, r} . We will design a mechanism Ms that is (6ε, 3eδ)-DP when restricted c s does not itself output a noisy version of to inputs x ∈ {0, 1}n with xi = 0 for i ∈ / L(T s ). The mechanism M c b with one coordinate m b u for each node u ∈ T s the prefix sums Ax. Instead, it outputs a vector Ms (x) = m with an even depth d(u) < h. c s draws three i.i.d. copies z(1) , z(2) , z(3) of the noise z of the mechanism In more detail, the mechanism M P (k) (k) Mo (x) = Ax+z. Let bu for u ∈ V(T ) be such that z(k) = u∈V(T ) bu χu . Then, for any d ∈ {0, . . . , h/2− 1} and node u ∈ T s with depth 2d, if sd+1 = r, let (k)

qu := median{br(u) − muℓ (∆<ℓ(ℓ(u)) (z(k) ), ∆<ℓ(r(u)) (z(k) ))}, k=1,2,3

(14)

c s set and let the mechanism M b u := qu + ar(u) . m Otherwise, if sd+1 = ℓ, let (k)

(k)

(k)

qu := median{br(ℓ(u)) − br(u) − br(r(u)) − mur (∆<r(ℓ(u)) (z(k) ), ∆<r(r(u)) (z(k) ))} k=1,2,3

and let the mechanism set b u := qu + ar(ℓ(u)) − ar(u) − ar(r(u)) . m 20

(15)

c s is (6ε, 3eδ)-DP when restricted to inputs x ∈ {0, 1}n with xi = 0 for Lemma 3. The mechanism M s i∈ / L(T ). (0)

(1)

Proof. Let x(0) , x(1) ∈ {0, 1}n be an arbitrary neighboring pair with xi = xi = 0 for i ∈ / L(T s ). Let (0) (1) s (0) (1) i ∈ L(T ) be the coordinate on which 0 = xi ̸= xi = 1. Given an x ∈ {x , x }, we argue that we can c s (x) as post-processing of M′ (x) = (Ax + z(1) , Ax + z(2) , Ax + z(3) ). By standard composition, obtain M o c s when restricted to inputs we have that the mechanism M′o is (6ε, 3eδ)-DP and thus the same holds for M x with xi = 0 for i ∈ / L(T s ). Note that our post-processing function depends on the pair x(0) , x(1) . This is sufficient because the DP inequality is checked separately for every neighboring pair. c s (x) from M′ (x), first compute for every node u ∈ V(T ) the value Now to obtain M o X X (0) a′u = xj = xj . j̸=i:u∈I(j)

j̸=i:u∈I(j)

Next, for k = 1, 2, 3, write Ax + z(k) in the basis χu as Ax + z(k) =

P

(k) u u∈V(T ) (au + bu )χ .

For each u,

(k) subtract a′u from (au + bu ) to obtain the value

b(k) u + 1{u ∈ I(i)}xi . Now consider any d ∈ {0, . . . , h/2 − 1} and node u ∈ T s with depth 2d. If sd+1 = r, then any leaf with an index i ∈ L(T s ) falls in either the subtree rooted at r(ℓ(u)) or r(r(u)). By definition of I(i), we get that I(i) is disjoint from V(T ℓ(ℓ(u)) ) ∪ V(T ℓ(r(u)) ) \ {ℓ(ℓ(u)), ℓ(r(u))}. Hence for v ∈ V(T ℓ(ℓ(u)) ) ∪ V(T ℓ(r(u)) ) \ {ℓ(ℓ(u)), ℓ(r(u))}, we have (k) b(k) v + 1{v ∈ I(i)}xi = bv . (k)

This allows us to obtain ∆<ℓ(ℓ(u)) (z(k) ) and ∆<ℓ(r(u)) (z(k) ). Finally, since we have av + bv v ∈ V(T ), we can compute

for every

(k)

median{ar(u) + br(u) − muℓ (∆<ℓ(ℓ(u)) (z(k) ), ∆<ℓ(r(u)) (z(k) ))} = k=1,2,3

(k)

median{br(u) − muℓ (∆<ℓ(ℓ(u)) (z(k) ), ∆<ℓ(r(u)) (z(k) ))} + ar(u) = k=1,2,3

b u. m Symmetrically, if sd+1 = ℓ, we have that I(i) is disjoint from V(T r(ℓ(u)) ) ∪ V(T r(r(u)) ) \ {r(ℓ(u)), r(r(u))}. (k) We can thus compute ∆<r(ℓ(u)) (z(k) ) and ∆<r(r(u)) (z(k) ). Again using that we know av + bv for every v ∈ V(T ), we can compute (k)

(k)

(k)

median{ar(ℓ(u)) − ar(u) − ar(r(u)) + br(ℓ(u)) − br(u) − br(r(u)) − mur (∆<r(ℓ(u)) (z(k) ), ∆<r(r(u)) (z(k) ))} = k=1,2,3

(k)

(k)

(k)

median{br(ℓ(u)) − br(u) − br(r(u)) − mur (∆<r(ℓ(u)) (z(k) ), ∆<r(r(u)) (z(k) ))} + ar(ℓ(u)) − ar(u) − ar(r(u)) = k=1,2,3

b u. m 2 b u has noise bounded roughly by σu, Next we argue that m . sg d+1

Lemma 4. For any u ∈ T s at an even depth 2d < h, we have if sd+1 = r (k)

2 E[median{br(u) − muℓ (∆<ℓ(ℓ(u)) (z(k) ), ∆<ℓ(r(u)) (z(k) ))}2 ] ≤ 3 · σu, , sg d+1 k=1,2,3

and if sd+1 = ℓ (k)

(k)

(k)

2 E[median{br(ℓ(u)) − br(u) − br(r(u)) − mur (∆<r(ℓ(u)) (z(k) ), ∆<r(r(u)) (z(k) ))}2 ] ≤ 3 · σu, . sg d+1 k=1,2,3

21

Lemma 4 follows almost immediately from Corollary 1 Proof of Lemma 4. Using Corollary 1 we have for u ∈ T s at depth 2d if sd+1 = r (k)

E[median{br(u) − muℓ (∆<ℓ(ℓ(u)) (z(k) ), ∆<ℓ(r(u)) (z(k) ))}2 ] ≤ k=1,2,3

(1)

3 · E[|br(u) − muℓ (∆<ℓ(ℓ(u)) (z(1) ), ∆<ℓ(r(u)) (z(1) ))|]2 = 2 2 . 3 · σu,ℓ = 3 · σu, sg d+1

and if sd+1 = ℓ (k)

(k)

(k)

E[median{br(ℓ(u)) − br(u) − br(r(u)) − mur (∆<r(ℓ(u)) (z(k) ), ∆<r(r(u)) (z(k) ))}2 ] ≤ k=1,2,3

(1)

(1)

(1)

3 · E[|br(ℓ(u)) − br(u) − br(r(u)) − mur (∆<r(ℓ(u)) (z(1) ), ∆<r(r(u)) (z(1) ))|]2 = 2 2 . 3 · σu,r = 3 · σu, sg d+1

c s . Based on our analysis of the residual noise above, we now construct an adversary Privacy Attacks on M c s via linear measurements, when that deduces the value of xi for a fixed i ∈ L(T s ) from the output of M σ is too small. Specifically, we show that for any J ⊆ {0, . . . , h/2 − 1} with |J | = h/4 and any {Jd }d∈J , with Jd consisting of half the nodes of T s at depth 2d for d > 0 and J0 = {ρ} if 0 ∈ J , there is at least one d ∈ J and one u ∈ Jd such that σu,sg is large. Inserting this in (13) implies that the ℓ∞ error of the d+1 original mechanism M is large. For fixed s ∈ {ℓ, r}h/2 , i ∈ L(T s ), J ⊆ {0, . . . , h/2 − 1} with |J | = h/4 and any {Jd }d∈J with Jd consisting of half the nodes of T s at depth 2d for d > 0 and J0 = {ρ} if 0 ∈ J , we design an adversary that c s (x), while knowing the values of the coordinates xj for j ̸= i. Since M c s (x) attempts to predict xi from M is (6ε, 3eδ)-DP for x that is zero for j ∈ / L(T s ), it must be the case that for any neighboring pair of inputs x′ , x′′ ∈ {0, 1}n with x′i = 0, x′′i = 1, x′j = x′′j = 0 for j ∈ / L(T s ), and x′j = x′′j for all j ̸= i, if x is chosen c s (x) with high probability, even when uniformly among {x′ , x′′ }, then no adversary can guess xi from M ′ ′′ ′ ′′ given knowledge of the pair {x , x }. Let x be uniform in {x , x }. We consider an adversary that estimates xi as in Algorithm 1. In essence, the adversary performs a privacy attack via linear measurements ψ i . The vectors ψ i are inspired by the Haar wavelet basis and are defined independently of x. The key step is to show that the vector ci computed by the adversary can be decomposed as ci = xi µi + r, where µi is a deterministic vector depending only on i, s, J , {Jd }d∈J , and r is a noise vector whose ℓ2 norm is controlled by σ. Given this decomposition, the adversary computes x̂i =

⟨ψ i , r⟩ ⟨ψ i , ci ⟩ = x + , i ⟨ψ i , µi ⟩ ⟨ψ i , µi ⟩

which is a private estimate of xi with additive noise ⟨ψ i , r⟩/⟨ψ i , µi ⟩. We now establish the decomposition ci = xi µi + r. P P For each u ∈ V(T ), let au = i:u∈I(i) xi so that Ax = u∈V(T ) au χu . For every d ∈ J and every u ∈ Jd , if sd+1 = r, the adversary subtracts X xj j̸=i:r(u)∈I(j)

22

cs Algorithm 1: Adversary for M c s (x) Input: s ∈ {ℓ, r}h/2 , i ∈ L(T s ), J , {Jd }d∈J , x′ , M Output: Estimate x̂i Initialize ciu = µiu = ψui = 0 for all u ∈ T s with even depth d(u) < h, and set ciΛ = µiΛ = 0 and i ψΛ = 2−h/4 ; for u ∈ T s with even depth 2d < h do if i ∈ L(T ℓ(u) ) then ψui = −2−(h/2−d)/2 ; else ψui = 2−(h/2−d)/2 ; end end for d ∈ J and u ∈ Jd do if sd+1 = r then   c s (x)u − P ci = 2−d/2 M x′ ; u j̸=i:r(u)∈I(j) µiu = 2−d/2 1{i ∈ L(T r(ℓ(u)) )};

j

else   P P ′ ′ ′ c s (x)u − P x + ciu = 2−d/2 M x + x j̸=i:r(ℓ(u))∈I(j) j j̸=i:r(u)∈I(j) j j̸=i:r(r(u))∈I(j) j ; µiu = −2−d/2 1{i ∈ L(T ℓ(r(u)) )}; end end i

i

⟨ψ ,c ⟩ Compute x̂i = ⟨ψ i ,µi ⟩ ; return x̂i ;

c s (x)u to obtain from M c s (x)u − M

X

X

xj = qu + ar(u) −

j̸=i:r(u)∈I(j)

xj = qu + 1{r(u) ∈ I(i)}xi ,

j̸=i:r(u)∈I(j)

where qu is defined as in (14). We observe that for sd+1 = r we have that i is in either the subtree rooted at r(ℓ(u)) or r(r(u)) and thus 1{r(u) ∈ I(i)} = 1{i ∈ L(T r(ℓ(u)) )}. The adversary has thus computed qu + 1{i ∈ L(T r(ℓ(u)) )}xi . Now multiply this by 2−d/2 to obtain   ciu = 2−d/2 qu + 1{i ∈ L(T r(ℓ(u)) )}xi . If instead sd+1 = ℓ, the adversary subtracts X xj − j̸=i:r(ℓ(u))∈I(j)

X j̸=i:r(u)∈I(j)

23

xj −

X j̸=i:r(r(u))∈I(j)

xj

c s (x)u to obtain from M 

 X

c s (x)u −  M

X

xj −

j̸=i:r(ℓ(u))∈I(j)

X

xj −

j̸=i:r(u)∈I(j)

xj  =

j̸=i:r(r(u))∈I(j)



 X

qu + ar(ℓ(u)) − ar(u) − ar(r(u)) − 

xj −

j̸=i:r(ℓ(u))∈I(j)

X

xj −

j̸=i:r(u)∈I(j)

X

xj  =

j̸=i:r(r(u))∈I(j)

qu + (1{r(ℓ(u)) ∈ I(i)} − 1{r(u) ∈ I(i)} − 1{r(r(u)) ∈ I(i)}) xi , where qu is defined in (15). Since for sd+1 = ℓ we have that i is either in the subtree rooted at ℓ(ℓ(u)) or at ℓ(r(u)), we conclude by the definition of I(i) that if i ∈ L(T ℓ(ℓ(u)) ), we have 1{r(ℓ(u)) ∈ I(i)} − 1{r(u) ∈ I(i)} − 1{r(r(u)) ∈ I(i)} = 1 − 1 − 0 = 0. and if i ∈ L(T ℓ(r(u)) ) we have 1{r(ℓ(u)) ∈ I(i)} − 1{r(u) ∈ I(i)} − 1{r(r(u)) ∈ I(i)} = 0 − 0 − 1 = −1. The adversary has thus computed qu − 1{i ∈ L(T ℓ(r(u)) )}xi . Now multiply this by 2−d/2 to obtain   ciu = 2−d/2 qu − 1{i ∈ L(T ℓ(r(u)) )}xi . Now define a vector r with one coordinate ru for each u ∈ T s at an even depth less than h and an additional dummy coordinate rΛ = 0. Define ru = 0 for u ∈ / ∪d∈J Jd and define ru = 2−d/2 qu otherwise. By i i the above arguments, c = xi µ + r, establishing the promised decomposition. For i ∈ L(T s ), the adversary computes the estimate ⟨ψ i , r + xi µi ⟩ ⟨ψ i , r⟩ ⟨ψ i , ci ⟩ = x + . x̂i = i i = i ⟨ψ , µ ⟩ ⟨ψ i , µi ⟩ ⟨ψ i , µi ⟩ c s (x) and x′ , it is (6ε, 3eδ)-differentially private by the postproSince x̂i is a deterministic function of M cessing property of differential privacy. Moreover, x̂i is an estimate of the binary variable xi with additive ⟨ψ i ,r⟩ noise ⟨ψ i ,µi ⟩ , which is independent of xi . This is because r only depends on s, J , {Jd }d∈J , and the noise vectors z(1) , z(2) , z(3) (which are independent of x because Mo is oblivious). We observe that none of ψ i , µi , r depend on x′ : ψ i depends on i and s, µi depends on i, s, J , {Jd }d∈J and r depends on s, J , {Jd }d∈J and the noise vectors z(1) , z(2) , z(3) . Applying Lemma 1, we conclude that for fixed s, i, J , {Jd }d∈J as defined above E[⟨ψ i , r⟩2 ] = Ω(min{6−2 ε−2 , (3e)−2 δ −2 }). ⟨ψ i , µi ⟩2 Therefore, for fixed s, J , {Jd }d∈J  X i∈L(T s )

E[⟨ψ i , r⟩2 ] = Ω 

 X

⟨ψ i , µi ⟩2 min{6−2 ε−2 , (3e)−2 δ −2 } .

(16)

i∈L(T s )

P P We now want to upper bound i∈L(T s ) E[⟨ψ i , r⟩2 ] and lower bound i∈L(T s ) ⟨ψ i , µi ⟩2 , which will give us a lower bound on σ. P We start by upper bounding i∈L(T s ) E[⟨ψ i , r⟩2 ]. Observe that the ψ i vectors are orthogonal and unit length. 24

Lemma 5. For i ∈ L(T s ) we have ∥ψ i ∥22 = 1 and for i ̸= j with i, j ∈ L(T s ), we have ⟨ψ i , ψ j ⟩ = 0. i This lemma follows directly from the definition proof hasPbeen deferred to Appendix B. It P of ψ and the follows from orthogonality and unit length that i∈L(T s ) E[⟨ψ i , r⟩2 ] = E[ i∈L(T s ) ⟨ψ i , r⟩2 ] ≤ E[∥r∥22 ]. Now recall that σ = maxd∈J maxu∈Jd σu,sg . We observe that d+1

E[∥r∥22 ] =

X X

E[r2u ]

d∈J u∈Jd

≤

X X

2 3 · 2−d · σu, sg d+1

d∈J u∈Jd

≤3·

X X

2−d · σ 2

d∈J u∈Jd

=3·

X

|Jd |2−d · σ 2

d∈J

= (3/2) ·

X

2d · 2−d · σ 2

d∈J

= (3/2) · |J | · σ 2 = (3/8) · h · σ 2 .

(17)

P i i 2 Next, we lower bound i∈L(T s ) ⟨ψ , µ ⟩ . Define for convenience the notation Anc(i, d) ∈ T as the ancestor of the i’th leaf at depth 2d. Let us next consider X ⟨ψ i , µi ⟩2 = i∈L(T s )

2



h/2−1

X

X 

i∈L(T s )

µiAnc(i,d) 2−(h/2−d)/2 (−1)1{i∈L(T

ℓ(Anc(i,d))

)} 

.

(18)

d=0

Let u = Anc(i, d) for short. Then µiu (−1)1{i∈L(T

ℓ(u)

)}

=

d+1 (u)) 2−d/2 (−1)1{sd+1 =ℓ} 1{i ∈ L(T sd+1 (sg )}(−1)1{i∈L(T

ℓ(u)

)}

.

d+1 (u)) Now consider first the case sd+1 = ℓ. Then 1{i ∈ L(T sd+1 (sg )} = 0 if i ∈ L(T ℓ(u) ). If instead r(u) i ∈ L(T ), we get ℓ(u) (−1)1{sd+1 =ℓ} (−1)1{i∈L(T )} = −1 · 1 = −1.

Similarly, if sd+1 = r, then we need only consider i ∈ L(T ℓ(u) ). Here we have (−1)1{sd+1 =ℓ} (−1)1{i∈L(T

ℓ(u)

)}

= 1 · (−1) = −1.

Thus in all circumstances, we may simplify µiu (−1)1{i∈L(T

ℓ(u)

)}

d+1 (u)) = −2−d/2 1{i ∈ L(T sd+1 (sg )}.

25

Inserting this in (18), we see that X ⟨ψ i , µi ⟩2 = i∈L(T s )



2

h/2−1

X

X

d+1 (Anc(i,d))) −2−h/4 1{i ∈ L(T sd+1 (sg )} =

 i∈L(T s )

d=0

2



h/2−1

X

2−h/2

X

d+1 (Anc(i,d))) 1{i ∈ L(T sd+1 (sg )} =

 i∈L(T s )

d=0 h/2−1 h/2−1

X

X

X

i∈L(T s ) d=0

d′ =0

2−h/2

′

sd′ +1 (Anc(i,d ))) d+1 (Anc(i,d))) 1{i ∈ L(T sd+1 (sg )}1{i ∈ L(T sd′ +1 (^ )} =

h/2−1 h/2−1

2−h/2

X

X X X

X

d=0

d′ =0 u∈Jd v∈Jd′ i∈L(T s )

sd′ +1 (v)) d+1 (u)) 1{i ∈ L(T sd+1 (sg )}1{i ∈ L(T sd′ +1 (^ )}.

Now define vectors ϕu for each u ∈ ∪d∈J Jd . If u is in depth 2d, we let ϕu be the indicator vector with one d+1 (u)) coordinate for each i ∈ L(T s ) taking the value 1{i ∈ L(T sd+1 (sg )}. Then by the above we have 2

X

i

i 2

X

−h/2

⟨ψ , µ ⟩ = 2

ϕ

u

u∈∪d∈J Jd

i∈L(T s )

. 2

Applying Cauchy-Schwartz, we first see that 2

2−h/2

X

≥2−h/2

ϕu

u∈∪d∈J Jd

2

X u∈∪d∈J Jd

2

· |L(T s )|−1 .

ϕu

(19)

1

u

Now using that the vectors ϕ are indicator vectors we have that (19) equals 2

 −h 

2

X

∥ϕ ∥1  = 2

u∈∪d∈J Jd

2

X

d−1 h/2−d−1

2

2

X X

u

∥ϕ ∥1

!2 −h

=2

d∈J u∈Jd

!2 −h

!2 −h

u

X X

h/2−d−1

2

=

d∈J u∈Jd

 2 = 2−h h · 2h/2−4 = 2−8 h2 .

d∈J

Therefore, X

⟨ψ i , µi ⟩2 ≥ 2−8 h2 .

(20)

i∈L(T s )

P Using the upper bound of E[∥r∥2 ] (17) and the lower bound of i∈L(T s ) ⟨ψ i , µi ⟩2 (20) in inequality (16), it follows that 3 · h · σ2 ≥ Ω(h2 · 2−8 min{6−2 ε−2 , (3e)−2 δ −2 }). 8 This gives a lower bound of √ σ 2 = Ω(h min{ε−2 , δ −2 }) ⇒ σ = Ω( h min{ε−1 , δ −1 }).

26

Inserting this in (10) and (13) we conclude  max E[∥M(x) − Ax∥∞ ] ≥ E[∥z∥∞ ] = Ω

x∈{0,1}n

h3/2 max{ε, δ}

 =Ω

log3/2 n max{ε, δ}

! .

This completes the proof of Theorem 1.

References [AFKT21] Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates in L1 geometry. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 393–403. PMLR, 2021. [AHP+ 24] Joel Daniel Andersson, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner, and Jalaj Upadhyay. Continual counting with gradual privacy expiration. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. [APT24]

Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy. CoRR, abs/2408.07021, 2024.

[AS17]

Naman Agarwal and Karan Singh. The price of differential privacy for online learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 32–40. PMLR, 2017.

[BDKT12] Aditya Bhaskara, Daniel Dadush, Ravishankar Krishnaswamy, and Kunal Talwar. Unconditional differentially private mechanisms for linear queries. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, page 1269–1284, New York, NY, USA, 2012. Association for Computing Machinery. [CDP+ 24] Christopher A. Choquette-Choo, Krishnamurthy Dj Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Guha Thakurta. Correlated noise provably beats independent noise for differentially private learning. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net, 2024. [CEM+ 25] Rachel Cummings, Alessandro Epasto, Jieming Mao, Tamalika Mukherjee, Tingting Ou, and Peilin Zhong. Differentially private space-efficient algorithms for counting distinct elements in the turnstile model. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025, volume 267 of Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2025. [CLN+ 24] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 July 3, 2023, Edmonton, Canada, Proceedings of Machine Learning Research, pages 1200–1222. PMLR, 2024.

27

[CSS10]

T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, Lecture Notes in Computer Science, pages 405–417. Springer, 2010.

[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, Lecture Notes in Computer Science, pages 265–284. Springer, 2006. [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 715–724. ACM, 2010. [DNRR15] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Tetsu Iwata and Jung Hee Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume 9453 of Lecture Notes in Computer Science, pages 735–751. Springer, 2015. [FHO21]

Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially private algorithms for graphs under continual observation. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, Lisbon, Portugal (Virtual Conference), September 6-8, 2021, volume 204 of LIPIcs, pages 42:1–42:16. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2021.

[FHU23]

Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learning Research, pages 10072–10092. PMLR, 2023.

[GV16]

Quan Geng and Pramod Viswanath. Optimal noise adding mechanisms for approximate differential privacy. IEEE Transactions on Information Theory, 62(2):952–969, 2016.

[HLL+ 22] Yuxuan Han, Zhicong Liang, Zhipeng Liang, Yang Wang, Yuan Yao, and Jiheng Zhang. Private streaming SCO in ℓp geometry with applications in high dimensional online decision making. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Proceedings of Machine Learning Research, pages 8249–8279. PMLR, 2022. [Hon15]

James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27, 2015.

[HSS24]

Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Private counting of distinct elements in the turnstile model and extensions. In Amit Kumar and Noga Ron-Zewi, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, London School of Economics, London, UK, August 28-30, 2024, volume 317 of LIPIcs, pages 40:1–40:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.

28

[HUU23]

Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, pages 5003–5039. SIAM, 2023.

[HUU24]

Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A unifying framework for differentially private sums under continual observation. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 995–1018. SIAM, 2024.

[JKR+ 23] Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023. [JKT12]

Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland, volume 23 of JMLR Proceedings, pages 24.1–24.34. JMLR.org, 2012.

[JRSS23]

Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, Proceedings of Machine Learning Research, pages 14654–14678. PMLR, 2023.

[KMS+ 21] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, pages 5213–5225. PMLR, 2021. [LPT21]

Kasper Green Larsen, Rasmus Pagh, and Jakub Tetek. Countsketches, feature hashing and the median of three. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 6011–6020. PMLR, 2021.

[MNT20]

Jirı́ Matousek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy. International Mathematics Research Notices, 2020(3):751–780, 02 2020.

[NTZ13]

Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 351–360. ACM, 2013.

[RS25]

Sofya Raskhodnikova and Teresa Anna Steiner. Fully dynamic algorithms for graph databases with edge differential privacy. Proc. ACM Manag. Data, 3(2):99:1–99:28, 2025.

[TS13]

Abhradeep Guha Thakurta and Adam D. Smith. (nearly) optimal algorithms for private online learning in full-information and bandit settings. In Christopher J. C. Burges, Léon Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 2733–2741, 2013. 29

A

Median-of-Three Trick

Here we show how to derive Corollary 1 from the work of [LPT21]. For the proof, we use the following auxiliary result by Larsen, Pagh and Tetek: Lemma 6 ([LPT21]). Let f : R+ → R+ be a non-increasing function and let t be a positive integer. Then t Z ∞ Z ∞ f (x)dx . f (x1/t )t dx ≤ x=0

x=0

Proof of Corollary 1. We have E[median{Z1 , Z2 , Z3 }2 ] ≤ E[min{|Z1 |, |Z2 |}2 ] + E[min{|Z1 |, |Z3 |}2 ] + E[min{|Z2 |, |Z3 |}2 ] = 3 · E[min{Z21 , Z22 }]. R∞ Let px = Pr[|Z1 | > x] and recall the layer-cake formula E[|Z1 |] = x=0 px dx. By independence of Z1 , Z2 , we get Z ∞ E[min{Z21 , Z22 }] ≤ Pr[Z21 > x ∧ Z22 > x]dx x=0 Z ∞ = Pr[Z21 > x]2 dx x=0 Z ∞ √ = Pr[|Z1 | > x]2 dx x=0

Letting f (x) = Pr[|Z1 | > x], we get from Lemma 6 that E[median{Z1 , Z2 , Z3 }2 ] ≤ 3 ·

Z ∞

2 Pr[|Z1 ] > x]dx

x=0

= 3 · E[|Z1 |]2 .

B

Properties of Attack Vectors

Here we prove Lemma 5, stating that the ψ i vectors are orthogonal and unit length. Proof of Lemma 5. Let i ̸= j with i, j ∈ L(T s ). Then X ℓ(u) ℓ(u) ⟨ψ i , ψ j ⟩ = 2−h/2 + 2−(h/2−d) (−1)1{i∈L(T )}+1{j∈L(T )} u:i,j∈L(T u )

If u denotes the lowest common ancestor of the i’th and j’th leaf, and u is at depth 2d, then u contributes −2−(h/2−d) to the inner product, the k’th ancestor of u contributes 2−k 2−(h/2−d) , and all other nodes contribute 0. Finally, the dummy coordinate contributes 2−h/2 . Hence the inner product precisely equals −2−(h/2−d) + 2−h/2 +

d X

2−k 2−(h/2−d) = −2−(h/2−d) + 2−h/2 + 2−(h/2−d) − 2−h/2 = 0.

k=1 i

Thus the ψ vectors are orthogonal. We also have h/2−1

∥ψ i ∥22 = 2−h/2 +

X d=0

30

2−(h/2−d) = 1.