Pith. sign in

REVIEW 1 major objections 5 minor 153 references

Edit-neighboring data streams still admit polylogarithmic-error private counting.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 09:34 UTC pith:EO2KCO3Z

load-bearing objection Strong paper introducing edit-neighboring streams with polylog-error mechanisms; the lower bounds hinge on an unproven external lemma that a referee should verify. the 1 major comments →

arxiv 2607.20727 v1 pith:EO2KCO3Z submitted 2026-07-22 cs.DS cs.CR

Edit-Neighboring Data Streams and Privacy under Continual Observation

Joel Daniel Andersson , Anamay Chaturvedi , Monika Henzinger , Roodabeh Safavi This is my paper
classification cs.DS cs.CR
keywords differential privacycontinual observationedit-neighboring streamscontinual countingfactorization mechanismsparse vector techniqueprefix-sum neighborslower bounds
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper asks what happens to differential privacy under continual observation when an individual's decision to participate can shift an entire data stream by one time-step, possibly causing a cascade of downstream shifts until an empty slot (⊥) absorbs the queue. It proves that every data-independent additive-noise mechanism—including the standard factorization counters—must incur polynomial error Ω̃(min{T^{1/3}/ε^{2/3}, T}) (or Ω(√T/ε) with pure DP) on such edit-neighboring streams. It then constructs the first mechanisms, SimECC and ECC, that achieve the same polylogarithmic additive error as the standard swap-neighboring setting, with only modestly worse constants, and a sparsity-adaptive version whose error depends on the number of non-⊥ values. A companion lower bound shows that an even more general notion—prefix-sum neighboring streams—cannot escape polynomial error for arbitrary mechanisms. Experiments on structured Bernoulli streams show the separation already appears at stream length 10^4.

Core claim

The paper's central claim is that participation-shift privacy (edit-neighboring DP) does not cost asymptotic accuracy: one can recover the standard swap-neighboring error bound O((1/ε) ln t √(ln(t/δ) ln(1/δ))) for continual counting. The catch is that this requires abandoning input-independent noise; any mechanism that adds noise to the prefix sums without looking at the input must pay polynomial error. The construction achieves the match by randomizing the checkpoints at which the counter updates, coupling those checkpoints across neighboring streams, and using a biased continual counter to schedule releases.

What carries the argument

The central object is the randomized checkpoint/bucket schedule: bucket sizes are drawn from a discrete Laplace distribution, so that an insertion shifts only a constant number of bucket sums under a coupling that matches checkpoints between neighboring streams. Around this, the mechanism layers a standard continual counter on the bucket sums and a 'biased' continual counter (which never underestimates) to release noisy checkpoints, so the randomization that absorbs the shift is hidden. On the lower-bound side, the hinge is the reduction from CountDistinct: difference streams of item-level neighboring cardinality streams are prefix-sum neighbors, so known CountDistinct hardness transfers.

Load-bearing premise

The entire result depends on the model in which a participation collision causes a cascade of shifts until the first empty slot (⊥), with a fixed horizon T discarding the last value; if real systems can instead absorb collisions by fine-grained time discretization, the problem—and both the lower and upper bounds—change.

What would settle it

A concrete check: build a data-independent additive-noise mechanism for {0,1,⊥}T that achieves sub-polynomial ℓ∞ error while satisfying (ε,δ)-DP for edit neighbors; or, alternatively, exhibit a specific pair of item-level neighboring CountDistinct streams whose difference streams violate the S1 condition of Lemma 7.5. Either would expose a gap in the lower-bound chain.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • Edit-neighboring DP is strictly stronger than swap-neighboring DP yet achieves the same order of additive error for continual counting; the price is only larger constants.
  • Any factorization-style, data-independent continual counter—the state of the art for the standard model—cannot be reused 'as is' for edit-neighboring streams; it must be randomized in an input-dependent way.
  • The sparsity-adaptive variant ECC shows that in sparse streams the leading error term depends only on the number of real values, not on the total time horizon T.
  • The prefix-sum-neighboring lower bound shows that reductions that map problems such as distinct-counting onto continual counting cannot escape polynomial error for arbitrary mechanisms.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper's shift-until-⊥ semantics are a modeling choice: if real systems can resolve collisions by fine-grained time discretization instead of shifting, the privacy threat largely dissolves—at an accuracy cost that the paper itself flags in §1.2. A testable extension is to quantify that accuracy cost for realistic arrival processes.
  • The lower bound inherits its force from two imported results (Jain et al. 2023a and a lemma attributed to Andersson et al. 2026). If that second lemma—that distinct-count difference streams lie in S1—fails for some adversarial stream family, both lower-bound theorems would need re-examination.
  • Because the lower bound applies only to data-independent mechanisms, the paper indirectly predicts that any near-optimal edit-private counter must make its noise depend on the input; a natural next step is to see whether input-dependent noise also helps in the standard swap model.
  • The empirical attack (a linear statistic over a known rate profile) is only one adversary; the authors themselves call it a 'simple' attack. A harder test would be a Bayesian or adaptive adversary that searches the output space—the gap between swap-private and edit-private counters under such an adversary is open.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper introduces a new adjacency notion for differential privacy under continual observation, called edit-neighboring streams, where one neighboring stream is obtained by inserting a value and shifting subsequent entries until the first ⊥ (or the end of the stream). The main claims are: (1) a lower bound showing that every data-independent additive-noise mechanism for edit-neighboring continual counting must incur polynomial ℓ∞ error; (2) upper-bound mechanisms SimECC and ECC, built from standard swap-neighboring continual counters as black boxes, that achieve the same polylogarithmic error as the standard setting, with ECC additionally being sparsity-adaptive; (3) a general lower bound for the more permissive prefix-sum-neighboring relation; and (4) synthetic experiments illustrating a practical separation. The formal results are Theorem 4.8/6.3 and Theorem 4.3/6.5 on the upper-bound side, and Theorems 1.2, 1.5, 7.6, 7.8, and 7.14 on the lower-bound side.

Significance. If the results are correct, the paper delivers a clean and nontrivial message: hiding participation shifts under continual observation need not cost asymptotic accuracy relative to the standard swap-neighboring model, but it does force a departure from input-independent noise to randomized, privately scheduled checkpoints. The upper-bound half is a genuine strength: the mechanisms are fully specified, all constants are fixed analytically (thresholds, privacy splits, noise scales), and the privacy/accuracy proofs are detailed and largely self-contained. The experimental section is honest, includes code, and explicitly states that the attack is a single natural attack rather than a claim of unconditional robustness. The lower-bound half is elegant and uses a sensitivity-set-containment framework that cleanly separates the edit-neighboring and prefix-sum-neighboring settings. However, the lower-bound chain depends on a pivotal lemma that is cited without proof, which is a load-bearing gap in the current manuscript.

major comments (1)
  1. [§7.1, Lemma 7.5] The lower bounds for Count(∼p,{-1,0,1}^T), Count(∼p,{0,1}^T), and consequently Theorems 1.2, 1.5, 7.6, 7.8 and 7.14 all hinge on Lemma 7.5, which asserts that for item-level neighboring CountDistinct streams, d(σ)-d(σ′) ∈ S1. This lemma is stated without proof and attributed to Andersson et al. (2026), a concurrent paper sharing a first author. Claim 7.4 is only a derivation from the S1 property; the S1 assertion is the actual content. If Lemma 7.5 is false, or if its neighboring definition differs from Definition 7.2 in a way that invalidates the transfer, the entire lower-bound half collapses. Please either include a self-contained proof of Lemma 7.5 in an appendix, or explicitly state the lower-bound theorems as conditional on this external result. As written, this is the single most important unresolved point in the paper.
minor comments (5)
  1. [§6, Lemma 6.2] The proof of part (ii) appears to yield a factor of e^ε rather than the stated e^{2ε}: two DLap shifts each give e^{ε/2}. Since e^ε ≤ e^{2ε}, the statement remains true, but the displayed derivation and the final bound should be aligned to avoid confusion.
  2. [Theorems 1.3/1.4 vs. Theorems 4.3/6.5] The informal theorems promise failure probability δ for all t, while the formal accuracy theorems condition on three separate events (EPart, CC accuracy, BCC accuracy). Please make the total failure-probability budget explicit, i.e., state how β, β_C, and β_B are chosen so that the union bound gives exactly the advertised 1−δ.
  3. [§2] The notation ECC is used both for the mechanism and for the error function of the underlying standard continual counter. This is confusing in the technical overview; consider renaming the error function (e.g., E_std).
  4. [Definition 4.1] In item 2, the definition of s_t as ∑_{i≤t} x_i omits the index bound; it should say s_t = ∑_{i=1}^t x_i with ⊥ treated as 0, and it is useful to set s_0 = 0.
  5. [§8, Table 1] The row for SimECC reports the same RMSE for Adv≤0.1 and Adv≤0.05. This is plausible because the attack advantage is already near zero at the smallest error setting, but the caption or text should state this explicitly so readers do not infer a typo.

Circularity Check

0 steps flagged

No material circularity: the upper bounds are self-contained and the lower-bound chain rests on external citations; the one self-cited lemma is load-bearing but is not a by-construction restatement of the paper's own inputs.

full rationale

The paper's central positive result (SimECC/ECC, Theorems 1.3 and 1.4, formalized as Theorems 4.8, 6.3, 6.5) is derived internally: the noise parameters, privacy splits, threshold τ, step-size μ, and SVT thresholds are all set analytically in the proofs, and the privacy analysis is carried out via explicit couplings (Definition 4.10, Lemma 4.14, Observation 4.13) proved in the paper or in Appendix B. The black-box continual counter (Lemma 3.12) is proved in Appendix A via the standard doubling trick, and the biased counter (Lemma 3.13) is constructed and proved there as well. No fitted parameter is renamed as a prediction, and the synthetic experiments are explicitly presented as illustrative ('this is not to suggest that SimECC is unconditionally robust'), so they do not function as evidence for the theorems. The lower-bound half is not circular in the sense prohibited here: it imports the CountDistinct lower bound from Jain et al. (2023a) as an external result and applies a group-privacy transfer. The one flagged item is Lemma 7.5, cited without proof from Andersson et al. (2026), a concurrent paper sharing the present first author. This lemma is genuinely load-bearing for Claim 7.4 and hence for Theorems 1.2, 1.5, 7.6, 7.8 and 7.14, and the manuscript does not re-derive it. However, this is a missing proof / missing-support concern, not a circularity: the lemma is not asserted to follow from the definitions or fitted quantities of this paper, and Claim 7.4's derivation from it is a straightforward implication of the S1 interval-sum condition. Because the cited result is external rather than a restatement of the paper's own construction, the derivation chain is not equivalent to its inputs by construction. No other pattern of circularity — self-definition, fitted-input-as-prediction, ansatz-smuggling, or renaming — appears in the manuscript.

Axiom & Free-Parameter Ledger

4 free parameters · 7 axioms · 0 invented entities

Positive results rest on standard DP primitives plus an assumed black-box standard continual counter (proved in Appendix A); lower bounds rest on two external results, one of which (Lemma 7.5, Andersson et al. 2026) is the first author's own cited theorem and is load-bearing. All numerical constants (τ, μ, privacy splits, SVT schedules) are set analytically in the proofs — none fitted to data. The edit-neighbor definition itself is the paper's postulate and carries the practical interpretation. No new entities (particles, forces, dimensions) are introduced; the ⊥ symbol is from Dong et al. (2023), and 'noisy checkpoints' / schedList / DLap bucket sizes are algorithmic constructions, not postulated entities with independent falsifiable handles.

free parameters (4)
  • ECC partition threshold τ = 1 + 408·ln(π²/(2δ))/ε with ε_p = ε/51
    Analytically set in Algorithm 2 / Theorem 4.8 so the good event E has probability ≥ 1 − δ/2 and each SVT-checkpointed bucket contributes ≥ 1 to the prefix sum (Lemma 4.4). Not fitted to data.
  • SimECC / SimPart step-size parameter μ = 3 + ⌈102·ln(2π²/(3δ))/ε⌉
    Analytically set in Section 6 so Lemma 6.2's bad-event probability is ≤ δ/2 and Lemma 6.4's bucket-gap bound holds. Not fitted to data.
  • Privacy budget split in ECC/SimECC = ε/51 (Part/SimPart); 4ε/27 (CC, δ_C = e^{−19ε/27}δ/16); 4ε/27 (BCC, δ_B = 2δ_C)
    Solved so that 17ε_p/3 + 4ε_C + 2ε_B = ε in the proof of Theorem 4.8; purely analytic accounting, no data involved.
  • SVT threshold schedule and noise scales in Algorithm 1 = threshold τ + 8 ln(t + 12/ε)/ε; Z0 ~ Lap(2/ε), Zt ~ Lap(4/ε)
    Inherited from the cited SVT variant (Lyu et al. 2017) and its accuracy tail bounds (Lemma 3.16); chosen to make the above/below-threshold gaps consistent. Not fitted to data.
axioms (7)
  • standard math Standard DP composition, group privacy, post-processing (Lemmas 3.5–3.7); analytic Gaussian mechanism (Lemma 3.4); SVT privacy and accuracy (Lemmas 3.15–3.16, Lyu et al. 2017).
    Used throughout Sections 4–7; cited from Dwork & Roth 2014, Balle & Wang 2018, Lyu et al. 2017.
  • domain assumption There exists a black-box (ε,δ)-DP continual counter for the 1-step 1-neighbor relation with error α_CC(t) = O(C_{ε,δ} ln t √(ln(t/β))) (Lemma 3.12).
    Proved in Appendix A by a doubling trick over a bounded factorization-based counter (Henzinger et al. 2025a); all ECC/SimECC accuracy and privacy guarantees inherit this as a primitive.
  • domain assumption Jain et al. (2023a) Theorem 1.7: item-level DP CountDistinct needs error Ω̃(min{T^{1/3}/ε^{2/3}, T}) when δ=o(ε/T) and Ω(min{√T/ε, T}) when δ=0, for (α, 1/100)-accurate mechanisms.
    Black-box external lower bound, transferred to the paper's CountDistinct variant in Theorem 7.3 via a 2-neighbor group-privacy argument at constant-factor cost.
  • domain assumption Andersson et al. (2026) Lemma 7.5: for item-level neighboring CountDistinct streams, d(σ) − d(σ') ∈ S1 = {v ∈ Z^T : every interval sum of v has absolute value ≤ 1}.
    Stated in Section 7.1 with a citation, not proved here; it is the load-bearing step for Claim 7.4 (d(σ) ∼_p d(σ')) from which both Theorems 1.2 and 1.5 follow. The source shares the present first author.
  • domain assumption Edit-neighbor semantics (Definition 3.11): an insertion shifts the suffix until the first ⊥; with no ⊥ the whole suffix shifts and the last element is dropped; inputs live in [0,1] ∪ {⊥} with ⊥ ≡ 0 for sums.
    The paper's proposed model of participation counterfactuals (queuing/collision example in §1); boundedness is needed to keep prefix-sum sensitivity finite. The realism of this model is a substantive premise for the practical narrative.
  • domain assumption Prefix-sum neighbor relation (Definitions 2.1 and 7.1): prefix differences are confined to {0,1} or to {0,−1} at every t.
    Definition imported from the CountDistinct reduction literature (Andersson et al. 2026; Jain et al. 2023a); it is the object of Theorem 1.5's general lower bound.
  • standard math SVT accuracy event (Lemma 3.16) holds for all instances simultaneously under the tuned failure schedule β_ℓ = 6β/(π²ℓ²).
    Laplace tail bounds plus union bound; used in Lemma 4.4 (checkpoint-count bound) and Theorem 4.3 (accuracy).

pith-pipeline@v1.3.0-alltime-deepseek · 70158 in / 38417 out tokens · 313240 ms · 2026-08-01T09:34:38.393997+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Edit-Neighboring Data Streams and Privacy under Continual Observation." pith.science (2026). https://pith.science/paper/EO2KCO3Z

@misc{pith2026260720727,
  author       = {Pith},
  title        = {Pith review of: Edit-Neighboring Data Streams and Privacy under Continual Observation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EO2KCO3Z}},
  note         = {Machine review of arXiv:2607.20727}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In this paper, we consider a more stringent notion of privacy compared to prior work wherein an individual's participation may shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length $T$, every additive-noise mechanism incurs error $\tilde{\Omega}(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ when required to be $\varepsilon$-DP under CO for edit-neighboring streams. This includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a `sweet-spot' in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams---which arises naturally in reductions for problems under CO---must incur additive error scaling as $\tilde{\Omega}(\min\{T^{1/3}/\varepsilon^{2/3}, T\})$ for any mechanism that is $\varepsilon$-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.

Figures

Figures reproduced from arXiv: 2607.20727 by Anamay Chaturvedi, Joel Daniel Andersson, Monika Henzinger, Roodabeh Safavi.

Figure 1
Figure 1. Figure 1: Plots evaluating mechanism performance on Bernoulli streams. [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Plots of (normalized) histograms over the statistic [PITH_FULL_IMAGE:figures/full_fig_p047_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Plots re-running the setup of Figure 1a but at T = 103 , different seeded randomness and slight parameter variations. The base setup is T = 1000, δ = 10−5 , alternating Bernoulli rates p ∈ {0.1, 0.9} T on blocks of width 10, with each point shown being the average over N = 20000 runs for one value of ε ∈ {0.10, 0.19, 0.38, 0.73, 1.4, 2.8, 5.4, 10, 20, 40, 77, 150}. The error bars on the per-run RMSE are sh… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

153 extracted references · 11 canonical work pages · 3 internal anchors

  1. [1]

    Differential Privacy on Dynamic Data

    Yuan Qiu and Ke Yi , title =. CoRR , volume =. 2022 , url =. doi:10.48550/ARXIV.2209.01387 , eprinttype =. 2209.01387 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2209.01387 2022

  2. [2]

    Monika Henzinger and A. R. Sricharan and Teresa Anna Steiner , editor =. Differentially Private Continual Release of Histograms and Related Queries , booktitle =. 2025 , url =

    2025

  3. [3]

    Privacy loss in

    Tang, Jun and Korolova, Aleksandra and Bai, Xiaolong and Wang, Xueqiang and Wang, Xiaofeng , journal=. Privacy loss in

  4. [4]

    Monika Henzinger and A. R. Sricharan and Teresa Anna Steiner , title =. CoRR , volume =. 2023 , url =. doi:10.48550/ARXIV.2302.11341 , eprinttype =. 2302.11341 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2302.11341 2023

  5. [5]

    arXiv preprint arXiv:2410.06266 , year=

    Near Exact Privacy Amplification for Matrix Mechanisms , author=. arXiv preprint arXiv:2410.06266 , year=

    Pith/arXiv arXiv

  6. [6]

    arXiv preprint arXiv:2408.07614 , year=

    Practical Considerations for Differential Privacy , author=. arXiv preprint arXiv:2408.07614 , year=

    Pith/arXiv arXiv

  7. [7]

    Count on Your Elders: Laplace vs Gaussian Noise , booktitle =

    Joel Daniel Andersson and Rasmus Pagh and Teresa Anna Steiner and Sahel Torkamani , editor =. Count on Your Elders: Laplace vs Gaussian Noise , booktitle =. 2025 , url =. doi:10.4230/LIPICS.FORC.2025.10 , timestamp =

    work page doi:10.4230/lipics.forc.2025.10 2025

  8. [8]

    2026 , issue_date =

    Andersson, Joel Daniel and Jain, Palak and Sivakumar, Satchit , title =. 2026 , issue_date =. doi:10.1145/3801902 , journal =

    work page doi:10.1145/3801902 2026

  9. [9]

    Brendan McMahan and Krishna Pillutla and Thomas Steinke and Abhradeep Thakurta , Booktitle =

    Krishnamurthy (Dj) Dvijotham and H. Brendan McMahan and Krishna Pillutla and Thomas Steinke and Abhradeep Thakurta , Booktitle =. Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy , Year =

  10. [10]

    Google AI Blog , year=

    Federated learning with formal differential privacy guarantees , author=. Google AI Blog , year=

  11. [11]

    International Conference on Machine Learning , pages=

    Practical and private (deep) learning without sampling or shuffling , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    2021

  12. [12]

    2019 , publisher=

    High-dimensional statistics: A non-asymptotic viewpoint , author=. 2019 , publisher=

    2019

  13. [13]

    Is interaction necessary for distributed private learning? , Year=

    Smith, Adam and Thakurta, Abhradeep and Upadhyay, Jalaj , Booktitle=. Is interaction necessary for distributed private learning? , Year=

  14. [14]

    Proceedings of the 16th International Conference on Database Theory , pages=

    Private decayed predicate sums on streams , author=. Proceedings of the 16th International Conference on Database Theory , pages=

  15. [15]

    Advances in Neural Information Processing Systems , volume=

    Improved differential privacy for sgd via optimal private linear operators on adaptive streams , author=. Advances in Neural Information Processing Systems , volume=

  16. [16]

    arXiv preprint arXiv:2210.01864 , year=

    Recycling scraps: Improving private learning by leveraging intermediate checkpoints , author=. arXiv preprint arXiv:2210.01864 , year=

    Pith/arXiv arXiv

  17. [17]

    Sergei Vassilvitskii , title =

  18. [18]

    arXiv preprint arXiv:2306.10428 , year=

    Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation , author=. arXiv preprint arXiv:2306.10428 , year=

    Pith/arXiv arXiv

  19. [19]

    14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , pages =

    Epasto, Alessandro and Mao, Jieming and Medina, Andres Munoz and Mirrokni, Vahab and Vassilvitskii, Sergei and Zhong, Peilin , title =. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , pages =. 2023 , volume =. doi:10.4230/LIPIcs.ITCS.2023.48 , annote =

    doi:10.4230/lipics.itcs.2023.48 2023

  20. [20]

    and McMahan, H

    Choquette-Choo, Christopher A. and McMahan, H. Brendan and Rush, Keith and Thakurta, Abhradeep , Booktitle =. Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning , Year =

  21. [21]

    Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Almost tight error bounds on differentially private continual counting , author=. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2023 , organization=

    2023

  22. [22]

    Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year=

    Improved Differentially Private Continual Observation Using Group Algebra , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , year=

    2025

  23. [23]

    Theory and Practice of Differential Privacy (TPDP 2015), London, UK , volume=

    Efficient use of differentially private binary trees , author=. Theory and Practice of Differential Privacy (TPDP 2015), London, UK , volume=

    2015

  24. [24]

    arXiv preprint arXiv:0904.0942 , year=

    Boosting the accuracy of differentially-private histograms through consistency , author=. arXiv preprint arXiv:0904.0942 , year=

    Pith/arXiv arXiv

  25. [25]

    Making Old Things New:

    Max Dupr. Making Old Things New:. Forty-first International Conference on Machine Learning,. 2024 , url =

    2024

  26. [26]

    Proceedings of SIGMOD International Conference on Management of data , pages=

    Differentially private aggregation of distributed time-series with transformation and encryption , author=. Proceedings of SIGMOD International Conference on Management of data , pages=

  27. [27]

    Network and Distributed Systems Security (NDSS) Symposium , year=

    Private continual release of real-valued data streams , author=. Network and Distributed Systems Security (NDSS) Symposium , year=

  28. [28]

    International Conference on Learning Representation , year=

    Correlated Noise Provably Beats Independent Noise for Differentially Private Learning , author=. International Conference on Learning Representation , year=

  29. [29]

    Advances in Neural Information Processing Systems , volume=

    (Amplified) Banded Matrix Factorization: A unified approach to private training , author=. Advances in Neural Information Processing Systems , volume=

  30. [30]

    Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security , pages=

    Pegasus: Data-adaptive differentially private stream processing , author=. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security , pages=

    2017

  31. [31]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    A unifying framework for differentially private sums under continual observation , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    2024

  32. [32]

    Frequency estimation under multiparty differential privacy: One-shot and streaming , Year =

    Huang, Ziyue and Qiu, Yuan and Yi, Ke and Cormode, Graham , Journal =. Frequency estimation under multiparty differential privacy: One-shot and streaming , Year =

  33. [33]

    Efficient algorithms for privately releasing marginals via convex relaxations , Volume =

    Dwork, Cynthia and Nikolov, Aleksandar and Talwar, Kunal , Journal =. Efficient algorithms for privately releasing marginals via convex relaxations , Volume =

  34. [34]

    Factorization norms and hereditary discrepancy , Volume =

    Matou. Factorization norms and hereditary discrepancy , Volume =. International Mathematics Research Notices , Number =

  35. [35]

    Sublinear Space Private Algorithms Under the Sliding Window Model , Year =

    Upadhyay, Jalaj , Booktitle =. Sublinear Space Private Algorithms Under the Sliding Window Model , Year =

  36. [36]

    Convex Optimization , Year =

    Boyd, Stephen and Vandenberghe, Lieven , Publisher =. Convex Optimization , Year =

  37. [37]

    Differentially private continual monitoring of heavy hitters from distributed streams , Year =

    Chan, T-H Hubert and Li, Mingfei and Shi, Elaine and Xu, Wenchang , Booktitle =. Differentially private continual monitoring of heavy hitters from distributed streams , Year =

  38. [38]

    The algorithmic foundations of differential privacy , Volume =

    Dwork, Cynthia and Roth, Aaron , Journal =. The algorithmic foundations of differential privacy , Volume =

  39. [39]

    Differentially Private Continual Release of Graph Statistics , Year =

    Song, Shuang and Little, Susan and Mehta, Sanjay and Vinterbo, Staal and Chaudhuri, Kamalika , Journal =. Differentially Private Continual Release of Graph Statistics , Year =

  40. [40]

    TCC , Date-Added =

    Cynthia Dwork and Frank McSherry and Kobbi Nissim and Adam Smith , Bibsource =. TCC , Date-Added =. 2006 , Bdsk-Url-1 =

    2006

  41. [41]

    Differentially private histograms under continual observation: Streaming selection into the unknown , Year =

    Cardoso, Adrian Rivera and Rogers, Ryan , Booktitle =. Differentially private histograms under continual observation: Streaming selection into the unknown , Year =

  42. [42]

    Differentially Private Algorithms for Graphs Under Continual Observation , Year =

    Hendrik Fichtenberger and Monika Henzinger and Lara Ost , Booktitle =. Differentially Private Algorithms for Graphs Under Continual Observation , Year =

  43. [43]

    Differentially Private Analysis on Graph Streams , Year =

    Upadhyay, Jalaj and Upadhyay, Sarvagya and Arora, Raman , Booktitle =. Differentially Private Analysis on Graph Streams , Year =

  44. [44]

    A Framework for Private Matrix Analysis in Sliding Window Model , Year =

    Upadhyay, Jalaj and Upadhyay, Sarvagya , Booktitle =. A Framework for Private Matrix Analysis in Sliding Window Model , Year =

  45. [45]

    The Price of Privacy for Low-rank Factorization , Year =

    Upadhyay, Jalaj , Booktitle =. The Price of Privacy for Low-rank Factorization , Year =

  46. [46]

    Private and Continual Release of Statistics , Url =

    T. Private and Continual Release of Statistics , Url =. 2011 , Bdsk-Url-1 =. doi:10.1145/2043621.2043626 , Journal =

    arXiv 2011

  47. [47]

    Maintaining Stream Statistics over Sliding Windows , Url =

    Mayur Datar and Aristides Gionis and Piotr Indyk and Rajeev Motwani , Bibsource =. Maintaining Stream Statistics over Sliding Windows , Url =. 2002 , Bdsk-Url-1 =. doi:10.1137/S0097539701398363 , Journal =

    work page doi:10.1137/s0097539701398363 2002

  48. [49]

    Near optimal linear algebra in the online and sliding window models , Year =

    Braverman, Vladimir and Drineas, Petros and Musco, Cameron and Musco, Christopher and Upadhyay, Jalaj and Woodruff, David P and Zhou, Samson , Booktitle =. Near optimal linear algebra in the online and sliding window models , Year =

  49. [50]

    Time-aware recommender systems: a comprehensive survey and analysis of existing evaluation protocols , Volume =

    Campos, Pedro G and D. Time-aware recommender systems: a comprehensive survey and analysis of existing evaluation protocols , Volume =. User Modeling and User-Adapted Interaction , Number =

  50. [51]

    Introduction to the non-asymptotic analysis of random matrices , Year =

    Vershynin, Roman , Booktitle =. Introduction to the non-asymptotic analysis of random matrices , Year =

  51. [52]

    Our data, ourselves: Privacy via distributed noise generation , Year =

    Dwork, Cynthia and Kenthapadi, Krishnaram and McSherry, Frank and Mironov, Ilya and Naor, Moni , Booktitle =. Our data, ourselves: Privacy via distributed noise generation , Year =

  52. [53]

    Frequency estimation over sliding windows , Year =

    Zhang, Linfeng and Guan, Yong , Booktitle =. Frequency estimation over sliding windows , Year =

  53. [54]

    Finding heavy hitters over the sliding window of a weighted data stream , Year =

    Hung, Regant YS and Ting, Hing-Fung , Booktitle =. Finding heavy hitters over the sliding window of a weighted data stream , Year =

  54. [55]

    Continuous monitoring of distributed data streams over a time-based sliding window , Volume =

    Chan, Ho-Leung and Lam, Tak-Wah and Lee, Lap-Kei and Ting, Hing-Fung , Date-Added =. Continuous monitoring of distributed data streams over a time-based sliding window , Volume =. Algorithmica , Number =

  55. [56]

    Optimal sampling from sliding windows , Volume =

    Braverman, Vladimir and Ostrovsky, Rafail and Zaniolo, Carlo , Date-Added =. Optimal sampling from sliding windows , Volume =. Journal of Computer and System Sciences , Number =

  56. [57]

    How to catch l2-heavy-hitters on sliding windows , Volume =

    Braverman, Vladimir and Gelles, Ran and Ostrovsky, Rafail , Date-Added =. How to catch l2-heavy-hitters on sliding windows , Volume =. Theoretical Computer Science , Pages =

  57. [58]

    Sampling from a moving window over streaming data , Year =

    Babcock, Brian and Datar, Mayur and Motwani, Rajeev , Booktitle =. Sampling from a moving window over streaming data , Year =

  58. [59]

    Approximate counts and quantiles over sliding windows , Year =

    Arasu, Arvind and Manku, Gurmeet Singh , Booktitle =. Approximate counts and quantiles over sliding windows , Year =

  59. [60]

    Muthukrishnan , Journal =

    S. Muthukrishnan , Journal =. Data Streams: Algorithms and Applications , Volume =

  60. [61]

    Garofalakis , Booktitle =

    Graham Cormode and Minos N. Garofalakis , Booktitle =. Streaming in a connected world: querying and tracking distributed data streams , Year =

  61. [62]

    Muthukrishnan , Journal =

    Graham Cormode and S. Muthukrishnan , Journal =. What's new: finding significant differences in network data streams , Volume =

  62. [63]

    Matrix completions, norms and Hadamard products , Volume =

    Mathias, Roy , Journal =. Matrix completions, norms and Hadamard products , Volume =

  63. [64]

    The power of factorization mechanisms in local and central differential privacy , Year =

    Edmonds, Alexander and Nikolov, Aleksandar and Ullman, Jonathan , Booktitle =. The power of factorization mechanisms in local and central differential privacy , Year =

  64. [65]

    Quantum circuits with mixed states , Year =

    Aharonov, Dorit and Kitaev, Alexei and Nisan, Noam , Booktitle =. Quantum circuits with mixed states , Year =

  65. [66]

    Differentially private online learning , Year =

    Jain, Prateek and Kothari, Pravesh and Thakurta, Abhradeep , Booktitle =. Differentially private online learning , Year =

  66. [67]

    Local privacy and statistical minimax rates , Year =

    Duchi, John C and Jordan, Michael I and Wainwright, Martin J , Booktitle =. Local privacy and statistical minimax rates , Year =

  67. [68]

    Chordal graphs and semidefinite optimization , Volume =

    Vandenberghe, Lieven and Andersen, Martin S , Journal =. Chordal graphs and semidefinite optimization , Volume =

  68. [69]

    Unconditional differentially private mechanisms for linear queries , Year =

    Bhaskara, Aditya and Dadush, Daniel and Krishnaswamy, Ravishankar and Talwar, Kunal , Booktitle =. Unconditional differentially private mechanisms for linear queries , Year =

  69. [70]

    A data-and workload-aware algorithm for range queries under differential privacy , Year =

    Li, Chao and Hay, Michael and Miklau, Gerome and Wang, Yue , Journal =. A data-and workload-aware algorithm for range queries under differential privacy , Year =

  70. [71]

    Operator Algebras and Mathematical Physics: 24th International Workshop in Operator Theory and Its Applications, Bangalore, December 2013 , Volume =

    Bhattacharyya, Tirthankar and Dritschel, Michael A , Publisher =. Operator Algebras and Mathematical Physics: 24th International Workshop in Operator Theory and Its Applications, Bangalore, December 2013 , Volume =

    2013

  71. [72]

    Optimal error of query sets under the differentially-private matrix mechanism , Year =

    Li, Chao and Miklau, Gerome , Booktitle =. Optimal error of query sets under the differentially-private matrix mechanism , Year =

  72. [73]

    The matrix mechanism: optimizing linear counting queries under differential privacy , Volume =

    Li, Chao and Miklau, Gerome and Hay, Michael and McGregor, Andrew and Rastogi, Vibhor , Journal =. The matrix mechanism: optimizing linear counting queries under differential privacy , Volume =

  73. [74]

    Differential privacy via wavelet transforms , Volume =

    Xiao, Xiaokui and Wang, Guozhang and Gehrke, Johannes , Journal =. Differential privacy via wavelet transforms , Volume =

  74. [75]

    Contravariant densities, complete distancesand relative fidelities for quantum channels , Volume =

    Belavkin, Viacheslav , Journal =. Contravariant densities, complete distancesand relative fidelities for quantum channels , Volume =

  75. [76]

    The Price of Differential Privacy under Continual Observation , Volume =

    Jain, Palak and Raskhodnikova, Sofya and Sivakumar, Satchit and Smith, Adam , Booktitle =. The Price of Differential Privacy under Continual Observation , Volume =

  76. [77]

    The Price of Differential Privacy under Continual Observation , Year =

    Jain, Palak and Raskhodnikova, Sofya and Sivakumar, Satchit and Smith, Adam , Journal =. The Price of Differential Privacy under Continual Observation , Year =

  77. [78]

    Differential Privacy: From Theory to Deployment,

    Thakurta, Abhradeep , Journal =. Differential Privacy: From Theory to Deployment,

  78. [79]

    Continuous Release of Data Streams under both Centralized and Local Differential Privacy , Year =

    Wang, Tianhao and Chen, Joann Qiongna and Zhang, Zhikun and Su, Dong and Cheng, Yueqiang and Li, Zhou and Li, Ninghui and Jha, Somesh , Booktitle =. Continuous Release of Data Streams under both Centralized and Local Differential Privacy , Year =

  79. [80]

    Differential privacy for growing databases , Volume =

    Cummings, Rachel and Krehbiel, Sara and Lai, Kevin A and Tantipongpipat, Uthaipon , Journal =. Differential privacy for growing databases , Volume =

  80. [81]

    Pure differential privacy for rectangle queries via private partitions , Year =

    Dwork, Cynthia and Naor, Moni and Reingold, Omer and Rothblum, Guy N , Booktitle =. Pure differential privacy for rectangle queries via private partitions , Year =

Showing first 80 references.