Pith. sign in

REVIEW 2 major objections 5 minor 68 references

A Simple and Robust Protocol for Distributed Counting

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read A simple variant of the classic randomized distributed-counting protocol is robust against white-box adaptive adversaries and achieves optimal communication complexity, while the original protocol is breakable by an explicit adaptive…

desk verdict The robust protocol is a genuine advance, but Theorem 2.1 (the HYZ12 attack) rests on a proof gap that needs fixing before the negative result is credible. read the letter →

arxiv 2509.05870 v1 pith:2T7FJKBC submitted 2025-09-06 cs.DC cs.DS

Edith Cohen , Moshe Shechner , Uri Stemmer This is my paper · ORCID
classification cs.DCcs.DS MSC 68W1568W20
keywords distributedcountingadaptiveadversarywhite-boxrobustnesscommunicationcomplexityrandomizedalgorithmsobliviousvssettinggeometricrandomvariablesfunctionalmonitoring
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper settles an open question about the distributed counting problem, in which a server must continuously estimate the total number of events occurring across $k$ sites while keeping communication small. The authors first show that the classic randomized protocol of [HYZ12], previously analyzed only against inputs fixed in advance, is not robust: an adaptive attack that feeds events to one site until the published estimate moves, then switches to the next site, drives the estimate to a positive bias of order $\sqrt{k}\,\varepsilon n$, far above the target accuracy $\varepsilon n$. They then present a slightly modified protocol that is robust even against a white-box adversary who sees the protocol's internal state, while achieving the optimal communication bound $O(\sqrt{k}/\varepsilon \cdot \log N)$. The resolution matters because it shows that, in this setting, robustness against adaptive inputs costs no extra communication and needs no external machinery such as differential privacy.

What carries the argument

The load-bearing object of the positive result is the round structure with exact-count synchronization: at the start of each round the server gathers the exact total $\bar{n}$, sets a transmission probability $p \approx \sqrt{k}/(\varepsilon \bar{n})$, and counts sample messages until exactly $k$ have arrived, so each round's event count is a sum of $k$ independent geometric variables with parameter $p$ and no estimation error carries across a round boundary. The robustness proof then rests on site-symmetry — server state is a function only of aggregate counts and message counts — which reduces every white-box adaptive adversary to an oblivious stream confined to one site. Inside a round, accuracy comes from a maximal partial-sum deviation bound for geometric variables (Claim 4.4), and a renewal-process analysis (Lemma 4.5) shows that for any fixed event index only $O(1)$ relevant rounds need to be considered, converting per-round accuracy into per-event accuracy without paying for a union bound over all rounds. On the attack side, the central object is the zero-inflated geometric variable $Z_{q,p} = B \cdot G$ with $B \sim \mathrm{Bernoulli}(1 - q/p)$ and $G \sim \mathrm{Geom}(q)$; its telescoping identity (Lemma 2.5) shows that the server's random round-boundary corrections preserve the attacker's bias exactly in distribution, and a Bernstein-type tail bound for sums of such variables (Lemma 2.6) controls the fluctuations.

What would settle it

Run the round-robin attack of Algorithm 3 against both protocols with $k = 256$, $\varepsilon = 0.125$, and $N = 10^5$, as the paper's simulations do. The attack theorem predicts HYZ12's relative error to climb toward $\sqrt{k}\,\varepsilon \approx 2$; repeated runs that keep the estimate within $[1-\varepsilon, 1+\varepsilon]\cdot n$ throughout would refute the bias-accumulation analysis. The robustness theorem predicts the new protocol's relative error stays below $\varepsilon = 0.125$ with high probability under the same attack; a median relative error that clearly exceeds $\varepsilon$ at any point in the second half of the run, across independent seeds, would refute the robustness guarantee.

Watch

Extended reading notes

Core claim

The paper makes two claims. First, the HYZ12 protocol loses accuracy under adaptively chosen inputs: for every event count $n \ge c_3\sqrt{k}/\varepsilon$, there is an attack under which $\Pr[\hat{n} - n > c_1\sqrt{k}\,\varepsilon n] \ge 1 - e^{-c_2 k}$. The attack exploits the protocol's per-site estimator, which is the last reported local count plus an expectation correction of roughly $1/p - 1$: the adversary injects events into one site until the published estimate changes, which reveals that the site has just reported, and then abandons that site, freezing a positive bias into its estimate; randomized adjustments at round boundaries preserve the expected bias, so it accumulates across sites. Second, a protocol that starts each round by collecting exact counts from every site and then counts only the number $B$ of sample messages — each site sends a ``1'' message with probability $p = \min\{1, c\sqrt{k}/(\varepsilon \bar{n})\}$ per event, the server estimates $\bar{n} + B/p$, and the round ends when $B$ reaches exactly $k$ — is robust in the white-box model with optimal communication. Robustness follows from site-symmetry: the server's state and outputs depend only on the total event count and the number of sample messages, never on which site sent them, so every adaptive placement of events is equivalent to an oblivious stream at a single site.

Load-bearing premise

The attack analysis assumes that every change the attacker observes in the published estimate is caused by a genuine Report message from the site it is currently feeding, so that the round-robin pointer stays synchronized with the reporting sites. If a round-boundary transition (a BoundaryReached alert or the server's random counter adjustment) moves the estimate without such a report, the claimed synchronization — and with it the bias-accumulation argument of Lemma 2.13 — no longer follows from the stated definitions.

Editorial extensions

If this is right

  • The HYZ12 protocol must not be used as-is when event streams can depend on published estimates; under the paper's attack its error scales as $\sqrt{k}\,\varepsilon n$, a factor $\sqrt{k}$ above the target.
  • Optimal communication and robustness are compatible in this problem: the new protocol matches the $\Omega(\sqrt{k}/\varepsilon \cdot \log N)$ lower-bound regime while remaining correct against white-box adaptive adversaries, making it the first to do so.
  • The new protocol avoids the differential-privacy layer that the previous robust protocol needed, and it removes the $\mathrm{polylog}(k)$ communication factor, while defending against a strictly stronger (white-box) attack model.
  • On non-adaptive streams the new protocol performs essentially like the classic one, so the robustness guarantee comes at no practical asymptotic cost; the paper's simulations show comparable communication and accuracy on uniform inputs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The site-symmetry argument is a general recipe: for distributed functional monitoring problems, any protocol whose server state depends only on aggregate counts and counts of protocol messages inherits robustness from its oblivious analysis, which may remove the need for privacy-based robustification in other tracking tasks.
  • The renewal-process conversion is a reusable tool: any round-based protocol whose round lengths are sums of light-tailed random variables can obtain per-time accuracy from per-round accuracy while considering only $O(1)$ relevant rounds, instead of union-bounding over all rounds.
  • The attack's effectiveness suggests a broader pattern — publishing an estimate built from per-site counters leaks exactly the timing information an adaptive adversary needs. A natural testable extension is to measure how much output perturbation (noise or coarsening) is required to break the round-robin attack against arbitrary per-site-counting protocols.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies the distributed counting problem under adaptive (white-box) adversaries. It makes two claims. First, it constructs an adaptive attack (Section 2) that is said to force the HYZ12 randomized protocol of Huang, Yi, and Zhang to fail with high probability, thereby showing that HYZ12 is not robust. Second, it presents a new protocol, called Robust (Algorithm 4), which is a simplified variant of the HYZ12 scheme and is proven to achieve ε-accuracy for every event index and uniformly over N events, with optimal communication O(√k/ε log N) for ε ≤ 1/√k. The robustness argument rests on a symmetry observation: the server's state and published estimate depend only on the total event count and the number of sampled report messages, not on which site generated the events. The accuracy analysis combines standard concentration bounds for geometric random variables with a renewal-process argument that converts per-round guarantees into per-event-index guarantees.

Significance. If the robust protocol result is correct, it is a significant advance: it gives the first protocol matching the optimal oblivious communication bound in the adaptive white-box setting, with a protocol that is arguably simpler than the prior robust construction of Xiong, Zhu, and Huang, and it resolves an open question explicitly raised in that work. The symmetry-based robustness proof is elegant and convincing, and the concentration arguments are standard. The negative result on HYZ12, if valid, would also be valuable, but the proof as written contains a load-bearing gap concerning the effect of boundary-triggered estimate changes on the attack's round-robin pointer. The positive contribution stands independently and is well supported; the negative contribution needs substantial repair or reframing.

major comments (2)
  1. [Section 2.4, Lemma 2.9] The proof of Lemma 2.9 asserts: 'Each update to the published estimate is caused by a Report message from the site currently injected by the attack.' This is false for Algorithm 2. When a BoundaryReached event occurs, the server subtracts the zero-inflated geometric random variable Z_i from every stored counter ¯n_i and republishes the estimate, so the value of ˆn can change without any Report message from the active site. Algorithm 3 only observes ˆn, so it cannot distinguish a boundary-induced change from a report-induced change and may advance its round-robin pointer prematurely. Consequently, the number R of distinct sites that actually send Report messages is not bounded below by the number of observed estimate changes, and the Chernoff bound applied to Bin(n0, √k/(4εn0)) does not bound R. Corollary 2.10's conclusion that R*_n ≥ k/2 therefore does not follow from the stated argument.
  2. [Section 2.4, Observation 2.12 and Lemma 2.13] Observation 2.12 claims that a reporting transcript, which fixes only the site-side randomness, uniquely determines the sequence of round-start indices, the configured probabilities, the states of the attack, and the event stream. This is incorrect: the attack's decisions are based on the published estimate ˆn, which depends on the server-side randomness Z_i used in the boundary adjustments. Because the event stream is itself a function of ˆn, fixing the site-side randomness alone does not fix the attack's behavior or the resulting event sequence. The conditioning argument in Lemma 2.13 is therefore circular. Additionally, the decomposition into one active site with m* events since its last report and k-1 sites with zero events since their last report is only valid if every pointer advance corresponds to a genuine report from the active site; boundary-induced advances break that decomposition. The bias lower bound in Lemma 2.13, and hence Theorem 2.1, is not established by the present proof.
minor comments (5)
  1. [Algorithm 2 and Observation 2.7] The expression 'p←2 min{0,⌊log2 √k/(εn')⌋}' appears to be missing the exponentiation: it should be 'p←2^{min{0,⌊log2(√k/(εn'))⌋}}' to denote a power of two. This typesetting issue also affects the display in Observation 2.7.
  2. [Lemma 2.13 proof] In the proof of Lemma 2.13, the text reads 'Since R*_n ≥ k/8', but the lemma assumes R*_n ≥ k/2. This appears to be a typo; the constants in the bias calculation should be checked for consistency once the attack proof is repaired.
  3. [Section 4.2.2, Lemma 4.2] The bit-complexity lemma is only sketched. In particular, the claim that each site can broadcast its value to an additive error of O(max{1, ε ¯n'/k}) and that this 'can be converted to a high probability or in-expectation bound' is vague and should be made precise, including how sites obtain the proxy ¯n'.
  4. [Definition 2.11] The term 'reporting transcript' is introduced informally. Since the subsequent analysis conditions on it, a formal definition of which site-side random variables are fixed (e.g., the Bernoulli samples at each site) would improve clarity and help expose the dependence issue raised above.
  5. [Section 6] The empirical section is informative, but the text could briefly note that the observed attack does not by itself constitute a proof of the theorem, and that the simulations of Robust use c=1 while the theoretical guarantees require a c that depends on the failure probability δ.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the robust protocol is analyzed directly from concentration bounds, and the attack bias is derived from explicit expectation calculations rather than from the claimed conclusions.

full rationale

The paper's derivation chain is self-contained. The robust protocol's accuracy is proved by bounding the partial sums of independent geometric random variables (Claim 4.4 applied with t = εn̄ and p = c√k/(εn̄)), its communication bound follows from a negative-binomial round-length argument (Lemma 4.1), and its robustness is obtained from the server's genuine site-symmetry: the server's estimate, round boundaries, and message count B depend only on the total event count and the anonymous ReportSample messages, not on which site produced an event. The attack on HYZ12 is not a fitted-input prediction: the claimed bias is computed from the explicit distribution of the last reported count and the zero-inflated geometric adjustments (Lemmas 2.5 and 2.6), and the simulation uses a fixed constant c=1 rather than a parameter fitted to the target output. Cited prior work, including works co-authored by the present authors, is used contextually to describe the robustification-via-DP literature and is not load-bearing in the proofs of Theorems 1.2 or 1.3. The possible concern about BoundaryReached updates changing the published estimate without a Report from the currently targeted site is a proof-correctness issue for the attack analysis, not a circular reduction: even if Lemma 2.9's synchronization claim fails, that would make the attack argument invalid, but it would not make any stated result equal to its own assumption by construction. No self-definitional, fitted-as-prediction, or self-citation-driven circularity is present.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new postulates or entities. It relies on standard concentration inequalities and a renewal-process argument. The only tunable algorithm parameter is the constant c in the transmission probability, which is a design choice rather than a fitted value.

free parameters (1)
  • protocol constant c = c = Θ(1) for Theorem 3.1; c = O(max{√(log(1/δ)), log(1/δ)/√k}) for Theorem 3.2
    The transmission probability p = min{1, c√k/(ε ¯n)} includes an arbitrary multiplicative constant c; the accuracy and communication bounds depend on it, but it is a fixed design constant, not fitted to data.
assumptions (3)
  • standard math Chernoff bound and Bernstein-type sub-exponential tail bounds for sums of independent geometric and zero-inflated geometric variables (Lemmas 2.2, 2.6, Claim 4.4, Eq. (4)).
    Used throughout the accuracy and attack analyses; these are textbook concentration inequalities.
  • standard math Doob's maximal inequality for non-negative submartingales (Claim A.1).
    Used to bound the maximum partial-sum deviation of geometric random variables in a round.
  • standard math Stochastic dominance and Wald's equation for nonnegative i.i.d. steps (Lemma 5.3).
    Used to bound the expected number of round starts in the window [t0, t] for the per-round to per-event conversion.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Simple and Robust Protocol for Distributed Counting." pith.science (2026). https://pith.science/paper/2T7FJKBC

@misc{pith2026250905870,
  author       = {Pith},
  title        = {Pith review of: A Simple and Robust Protocol for Distributed Counting},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2T7FJKBC}},
  note         = {Machine review of arXiv:2509.05870}
}
abstract

We revisit the distributed counting problem, where a server must continuously approximate the total number of events occurring across $k$ sites while minimizing communication. The communication complexity of this problem is known to be $\Theta(\frac{k}{\epsilon}\log N)$ for deterministic protocols. Huang, Yi, and Zhang (2012) showed that randomization can reduce this to $\Theta(\frac{\sqrt{k}}{\epsilon}\log N)$, but their analysis is restricted to the {\em oblivious setting}, where the stream of events is independent of the protocol's outputs. Xiong, Zhu, and Huang (2023) presented a robust protocol for distributed counting that removes the oblivious assumption. However, their communication complexity is suboptimal by a $polylog(k)$ factor and their protocol is substantially more complex than the oblivious protocol of Huang et al. (2012). This left open a natural question: could it be that the simple protocol of Huang et al. (2012) is already robust? We resolve this question with two main contributions. First, we show that the protocol of Huang et al. (2012) is itself not robust by constructing an explicit adaptive attack that forces it to lose its accuracy. Second, we present a new, surprisingly simple, robust protocol for distributed counting that achieves the optimal communication complexity of $O(\frac{\sqrt{k}}{\epsilon} \log N)$. Our protocol is simpler than that of Xiong et al. (2023), perhaps even simpler than that of Huang et al. (2012), and is the first to match the optimal oblivious complexity in the adaptive setting.

Figures

Figures reproduced from arXiv: 2509.05870 by the authors.

Figure 1
Figure 1. HYZ12 under uniform (dashed) vs. attack (solid). k = 64, 256, ε = 0.125, r = 40. 0 25000 50000 75000 100000 125000 150000 175000 200000 Events 0 500 1000 1500 2000 2500 3000 3500 Cumulative messages ROBUST Communication k=64, = 0.125, r=40, c=1.0 Uniform (median) Attack (median) Attack Uniform (median) 0 20000 40000 60000 80000 100000 Events 0 1000 2000 3000 4000 5000 6000 7000 Cumulative messages ROBUST Communicati… view at source ↗
Figure 2
Figure 2. Robust under uniform (dashed) vs. attack (solid). k = 64, 256, ε = 0.125, r = 40. We observe that for the adaptive attack inputs, Robust uniformly dominates; for uniform inputs, the curves are incomparable: HYZ12 is favored in the very low ε ≪ 1/ √ k regime while Robust is better in the moderate ε regime. Recall that both protocols have the same asymptotic guarantees. References [ABC09] Chrisil Arackaparambil, Joshu… view at source ↗
Figure 3
Figure 3. Communication vs. accuracy tradeoff (median with (5%,95% bands) for [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

68 extracted references · 64 canonical work pages

  1. [1]

    Functional monitoring without monotonicity

    Chrisil Arackaparambil, Joshua Brody, and Amit Chakrabarti. Functional monitoring without monotonicity. In International Colloquium on Automata, Languages, and Programming , pages 95--106. Springer, 2009

    work page 2009

  2. [2]

    Adversarial laws of large numbers and optimal regret in online classification

    Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. pages 447--455, 2021

    work page 2021

  3. [3]

    A framework for adversarial streaming via differential privacy and difference estimators

    Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial streaming via differential privacy and difference estimators. CoRR , abs/2107.14527, 2021

    arXiv 2021

  4. [4]

    Rounds vs communication tradeoffs for maximal independent sets

    Sepehr Assadi, Gillat Kol, and Zhijun Zhang. Rounds vs communication tradeoffs for maximal independent sets. In FOCS , 2022

    work page 2022

  5. [5]

    Deterministic decremental single source shortest paths: beyond the O (mn) bound

    Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the O (mn) bound. In STOC , 2016

    work page 2016

  6. [6]

    Deterministic partially dynamic single source shortest paths for sparse graphs

    Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In SODA , 2017

    work page 2017

  7. [7]

    A framework for adversarially robust streaming algorithms

    Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In PODS , 2020

    work page 2020

  8. [8]

    Adversarially robust streaming via dense-sparse trade-offs

    Omri Ben - Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In SOSA , 2022

    work page 2022

Show all 68 references
  1. [9]

    Deterministic partially dynamic single source shortest paths in weighted graphs

    Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In ICALP , 2017

    2017

  2. [10]

    Italiano

    Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In SODA , 2015

    2015

  3. [11]

    Adversarial robustness of streaming algorithms through importance sampling

    Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In NeurIPS , 2021

    2021

  4. [12]

    New deterministic approximation algorithms for fully dynamic matching

    Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC , 2016

    2016

  5. [13]

    Fully dynamic approximate maximum matching and minimum vertex cover in O(log\( ^ 3 \) n) worst case update time

    Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log\( ^ 3 \) n) worst case update time. In SODA , 2017

    2017

  6. [14]

    Deterministically maintaining a (2+ ) -approximate minimum vertex cover in O (1/ ^2) amortized update time

    Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2+ ) -approximate minimum vertex cover in O (1/ ^2) amortized update time. In SODA , 2019

    2019

  7. [15]

    Deterministic rounding of dynamic fractional matchings

    Sayan Bhattacharya and Peter Kiss. Deterministic rounding of dynamic fractional matchings. In ICALP , 2021

    2021

  8. [16]

    Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds

    Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In STOC , 2022

    2022

  9. [17]

    Concentration Inequalities: A Nonasymptotic Theory of Independence

    Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence . Oxford University Press, 2013

    2013

  10. [18]

    Smith, Thomas Steinke, Uri Stemmer, and Jonathan R

    Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. In STOC , 2016

    2016

  11. [19]

    A rounds vs

    Mark Braverman and Rotem Oshman. A rounds vs. communication tradeoff for multi-party set disjointness. In FOCS , 2017

    2017

  12. [20]

    A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond

    Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In FOCS , 2020

    2020

  13. [21]

    Holistic aggregates in a networked world: Distributed tracking of approximate quantiles

    Graham Cormode, Minos Garofalakis, Shanmugavelayutham Muthukrishnan, and Rajeev Rastogi. Holistic aggregates in a networked world: Distributed tracking of approximate quantiles. In SIGMOD , 2005

    2005

  14. [22]

    Adversarially robust coloring for graph streams

    Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In ITCS , 2022

    2022

  15. [23]

    Decremental all-pairs shortest paths in deterministic near-linear time

    Julia Chuzhoy. Decremental all-pairs shortest paths in deterministic near-linear time. In STOC , 2021

    2021

  16. [24]

    A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems

    Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In STOC , 2019

    2019

  17. [25]

    On the robustness of countsketch to adaptive inputs

    Edith Cohen, Xin Lyu, Jelani Nelson, Tam \' a s Sarl \' o s, Moshe Shechner, and Uri Stemmer. On the robustness of countsketch to adaptive inputs. In ICML , 2022

    2022

  18. [26]

    Muthukrishnan, and Ke Yi

    Graham Cormode, S. Muthukrishnan, and Ke Yi. Algorithms for distributed functional monitoring. In SODA , 2008

    2008

  19. [27]

    Continuous sampling from distributed streams

    Graham Cormode, Shanmugavelayutham Muthukrishnan, Ke Yi, and Qin Zhang. Continuous sampling from distributed streams. Journal of the ACM (JACM) , 2012

    2012

  20. [28]

    The continuous distributed monitoring model

    Graham Cormode. The continuous distributed monitoring model. ACM SIGMOD Record , 2013

    2013

  21. [29]

    Deterministic algorithms for decremental shortest paths via layered core decomposition

    Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In SODA , 2021

    2021

  22. [30]

    Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou

    Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou. Robust algorithms on adaptive inputs from bounded adversaries. In ICLR , 2023

    2023

  23. [31]

    Improved algorithms for distributed entropy monitoring

    Jiecao Chen and Qin Zhang. Improved algorithms for distributed entropy monitoring. Algorithmica , 2017

    2017

  24. [32]

    Multiparty communication complexity

    Danny Dolev and Tom \'a s Feder. Multiparty communication complexity . IBM Thomas J. Watson Research Division Yorktown Heights, NY, USA, 1989

    1989

  25. [33]

    Preserving statistical validity in adaptive data analysis

    Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In STOC , 2015

    2015

  26. [34]

    Rothblum

    Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC , 2010

    2010

  27. [35]

    On the complexity of differentially private data release: efficient algorithms and hardness results

    Cynthia Dwork, Moni Naor, Omer Reingold, Guy N Rothblum, and Salil Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC , 2009

    2009

  28. [36]

    Efficient reactive monitoring

    Mark Dilman and Danny Raz. Efficient reactive monitoring. IEEE journal on selected areas in communications , 20(4):668--676, 2002

    2002

  29. [37]

    Optimal communication bounds for classic functions in the coordinator model and beyond

    Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P Woodruff, and Peilin Zhong. Optimal communication bounds for classic functions in the coordinator model and beyond. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1911--1922, 2024

    1911

  30. [38]

    Adaptive machine unlearning

    Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi - Malvajerdi, and Chris Waites. Adaptive machine unlearning. In NeurIPS , 2021

    2021

  31. [39]

    New algorithms and hardness for incremental single-source shortest paths in directed graphs

    Maximilian Probst Gutenberg, Virginia Vassilevska Williams , and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In STOC , 2020

    2020

  32. [40]

    Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary

    Maximilian Probst Gutenberg and Christian Wulff - Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In SODA , 2020

    2020

  33. [41]

    Deterministic algorithms for decremental approximate shortest paths: Faster and simpler

    Maximilian Probst Gutenberg and Christian Wulff - Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In SODA , 2020

    2020

  34. [42]

    Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

    Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM) , 2001

    2001

  35. [43]

    Adversarially robust streaming algorithms via differential privacy

    Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In NeurIPS , 2020

    2020

  36. [44]

    Communication-efficient distributed covariance sketch, with application to distributed pca

    Zengfeng Huang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. Communication-efficient distributed covariance sketch, with application to distributed pca. Journal of Machine Learning Research , 22(80):1--38, 2021

    2021

  37. [45]

    Moritz Hardt and Jonathan R. Ullman. Preventing false discovery in interactive data analysis is hard. In FOCS , 2014

    2014

  38. [46]

    Simple and optimal algorithms for heavy hitters and frequency moments in distributed models

    Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu, and Zhewei Wei. Simple and optimal algorithms for heavy hitters and frequency moments in distributed models. In STOC , 2025

    2025

  39. [47]

    The communication complexity of distributed epsilon-approximations

    Zengfeng Huang and Ke Yi. The communication complexity of distributed epsilon-approximations. SIAM Journal on Computing , 46(4):1370--1394, 2017

    2017

  40. [48]

    Randomized algorithms for tracking distributed count, frequencies, and ranks

    Zengfeng Huang, Ke Yi, and Qin Zhang. Randomized algorithms for tracking distributed count, frequencies, and ranks. In PODS , 2012

    2012

  41. [49]

    Communication-efficient distributed monitoring of thresholded counts

    Ram Keralapura, Graham Cormode, and Jeyashankher Ramamirtham. Communication-efficient distributed monitoring of thresholded counts. In SIGMOD , 2006

    2006

  42. [50]

    Separating adaptive streaming from oblivious streaming using the bounded storage model

    Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. In CRYPTO , 2021

    2021

  43. [51]

    Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis

    Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis . Cambridge university press, 2017

    2017

  44. [52]

    Dynamic spanning forest with worst-case update time: adaptive, L as vegas, and O (n^ 1/2- ) -time

    Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, L as vegas, and O (n^ 1/2- ) -time. In STOC , 2017

    2017

  45. [53]

    Dynamic minimum spanning forest with subpolynomial worst-case update time

    Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff - Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In FOCS , 2017

    2017

  46. [54]

    Lower bounds for number-in-hand multiparty communication complexity, made easy

    Jeff M Phillips, Elad Verbin, and Qin Zhang. Lower bounds for number-in-hand multiparty communication complexity, made easy. In SODA , 2012

    2012

  47. [55]

    Relaxed models for adversarial streaming: The bounded interruptions model and the advice model

    Menachem Sadigurschi, Moshe Shechner, and Uri Stemmer. Relaxed models for adversarial streaming: The bounded interruptions model and the advice model. In ESA , 2023

    2023

  48. [56]

    Tight lower bounds for differentially private selection

    Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In FOCS , 2017

    2017

  49. [57]

    Optimal random sampling from distributed streams revisited

    Srikanta Tirthapura and David P Woodruff. Optimal random sampling from distributed streams revisited. In DISC , 2011

    2011

  50. [58]

    Liu, Richard Peng, and Aaron Sidford

    Jan van den Brand, Yu Gao, Arun Jambulapati, Yin Tat Lee, Yang P. Liu, Richard Peng, and Aaron Sidford. Faster maxflow via improved dynamic spectral vertex sparsifiers. In STOC , 2022

    2022

  51. [59]

    The communication complexity of addition

    Emanuele Viola. The communication complexity of addition. Combinatorica , 35(6):703--747, 2015

    2015

  52. [60]

    Rounding dynamic matchings against an adaptive adversary

    David Wajc. Rounding dynamic matchings against an adaptive adversary. In STOC , 2020

    2020

  53. [61]

    Learning based distributed tracking

    Hao Wu, Junhao Gan, and Rui Zhang. Learning based distributed tracking. In KDD , 2020

    2020

  54. [62]

    Fully-dynamic minimum spanning forest with improved worst-case update time

    Christian Wulff - Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In STOC , 2017

    2017

  55. [63]

    Tight bounds for distributed functional monitoring

    David P Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In STOC , 2012

    2012

  56. [64]

    When distributed computation does not help

    David P Woodruff and Qin Zhang. When distributed computation does not help. CoRR, abs/1304.4636 , 5, 2013

    2013 arXiv

  57. [65]

    An optimal lower bound for distinct elements in the message passing model

    David P Woodruff and Qin Zhang. An optimal lower bound for distinct elements in the message passing model. In SODA , 2014

    2014

  58. [66]

    Woodruff and Samson Zhou

    David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In FOCS , 2021

    2021

  59. [67]

    Adversarially robust distributed count tracking via partial differential privacy

    Zhongzheng Xiong, Xiaoyi Zhu, and Zengfeng Huang. Adversarially robust distributed count tracking via partial differential privacy. In NeurIPS , 2023

    2023

  60. [68]

    Optimal tracking of distributed heavy hitters and quantiles

    Ke Yi and Qin Zhang. Optimal tracking of distributed heavy hitters and quantiles. In PODS , 2009

    2009

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.