Pith. sign in

REVIEW 3 major objections 7 minor 59 references

Load Balancing under Adaptive Bin Deletions

T0 review · 3 major / 7 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Classical load-balancing bounds survive adaptive bin deletions

desk verdict Resolves the partial-deletion regime of the adaptive bin-deletion game from FKS25. The coupling technique is clean and correct; the 2-split analysis is novel but has a real gap in the maximum-load bound. read the letter →

arxiv 2607.06211 v1 pith:UWTV4K7B submitted 2026-07-07 cs.DS

Haim Kaplan , Shay Sapir , Uri Stemmer This is my paper · ORCID
classification cs.DS
keywords ballsandbinsloadbalancingadaptiveadversarypoweroftwochoicesstochasticdominationcouplingargumentbindeletionrecourse
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 studies a balls-and-bins game where an adaptive adversary deletes bins one at a time and the algorithm must redistribute displaced balls among surviving bins. The authors prove that after n/2 deletion rounds, uniform random redistribution achieves O(n) total ball movements (recourse) and O(log n / log log n) maximum load, matching the classical static balls-and-bins bound. Applying the power of two choices—placing each ball in the less loaded of two random bins—reduces the maximum load to O(log log n) while maintaining linear recourse. These results resolve an open question about partial deletions: the classical load-balancing guarantees carry over to the adaptive setting for up to half the bins. The authors then consider a more restrictive variant where a deleted bin can only send its balls to d random bins. Keeping all balls together (d=1) fails catastrophically against an adaptive adversary but works well against an oblivious one, where the problem maps to a random forest whose tree sizes and depths govern load and recourse. Splitting into just two groups (d=2) suffices to recover linear recourse and polylogarithmic maximum load against an adaptive adversary, though the load bound holds only with constant probability. The central technique is a coupling argument that reduces each phase of the adaptive game to a non-adaptive ball-throwing process, showing the adaptive configuration is stochastically dominated by the non-adaptive one.

What carries the argument

Coupling between adaptive and non-adaptive balls-and-bins games via stochastic domination (Lemma 1.7 / Lemma 3.3); phase decomposition where each phase halves the number of surviving bins; Teflon ball hybrid game sequence connecting 2-split to a paid-uniform game; exponential potential function for 2-split maximum load; random forest equivalence for oblivious 1-split; Galton-Watson domination for tree-size bounds.

What would settle it

If one could exhibit an adaptive adversary that, against uniform redistribution over n/2 rounds, forces maximum load exceeding O(log n / log log n) or total recourse exceeding O(n) with non-negligible probability, the main theorem would fail.

Watch

Extended reading notes

Core claim

The paper's central object is a coupling between the adaptive bin-deletion game and a non-adaptive balls-and-bins process. The coupling works by simulating the adaptive game inside the non-adaptive one: when a ball is thrown in the non-adaptive game and lands in a bin corresponding to an already-deleted adaptive bin, it is re-thrown. This maintains a load invariant ensuring the non-adaptive game's configuration pointwise dominates the adaptive game's. Because the non-adaptive game cannot terminate before the adaptive phase completes (right before the last deletion of a phase, there are always enough surviving bins that some subset has fewer than n balls), the adaptive recourse and maximum负载都

Load-bearing premise

The coupling argument depends on a phase structure where each phase halves the number of bins, and the key stopping-condition argument requires that right before the last deletion of a phase, the surviving bins contain few enough total balls that some subset must be below threshold. For the 2-split variant, the maximum load bound holds only with constant probability rather than high probability, and extending 2-split results beyond n/2 rounds remains open.

Editorial extensions

If this is right

  • For distributed systems where servers fail adaptively, uniform redistribution after failures is provably near-optimal for up to half the servers, requiring only linear total work.
  • The power of two choices retains its exponential load improvement even under adversarial server removals, suggesting two-choice hashing schemes are robust to adaptive failures.
  • The 2-split result shows that even bandwidth-constrained nodes (connecting to only 2 targets per failure) can maintain efficient load balancing against adaptive adversaries.
  • The separation between d=1 (catastrophic) and d=2 (sufficient) against adaptive adversaries identifies a sharp threshold for how much decentralization is needed under adversarial conditions.
  • The random forest equivalence for oblivious 1-split connects load balancing to branching process theory, providing tools for analyzing related merge-based redistribution schemes.

Reading between the lines

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

  • The phase-based coupling structure suggests that for T between n/2 and n, the maximum load should interpolate smoothly between O(log n / log log n) and the trivial O(n), with the transition governed by the number of remaining bins per phase—a prediction consistent with the general theorem stated for all T ≤ n−1.
  • The constant-probability (rather than high-probability) guarantee for 2-split maximum load likely stems from the exponential potential function's multiplicative failure mode; a more refined potential or a layered induction might boost this to high probability, though the paper does not attempt this.
  • The Teflon ball technique—gradually converting correlated group movements into independent ones while paying a logarithmic overhead—could generalize to other settings where correlated random choices must be decoupled under adaptive observation.
  • The d=1 vs d=2 separation hints at a general principle: against adaptive adversaries, any fixed number of correlated moves below a threshold allows snowball attacks, while splitting into just two independent streams suffices to break the feedback loop.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

3 major / 7 minor

Summary. This paper studies an adaptive bin-deletion game where an adversary sequentially deletes bins and the algorithm must redistribute balls to surviving bins. The main results (Theorem 3.1 and Theorem 3.5) show that for T = n/2 rounds, uniform random redistribution achieves O(n) recourse and O(log n / log log n) maximum load, while the power of two choices achieves O(n) recourse and O(log log n) maximum load, both with high probability. These results resolve an open question of Fine et al. [FKS25] regarding partial deletions. The paper also analyzes a d-split variant: d=1 fails against adaptive adversaries but succeeds against oblivious ones (Theorem 5.1), and d=2 suffices for O(n) recourse (w.h.p.) and poly(log n) maximum load (constant probability) against adaptive adversaries (Theorem 4.1, Theorem 4.8). The proofs use coupling arguments to reduce adaptive games to non-adaptive games with appropriate stopping conditions, a hybrid/Teflon-ball construction for the 2-split recourse bound, and a potential function argument for the 2-split maximum load.

Significance. The paper resolves a natural and explicitly stated open question from FKS25 regarding the regime of partial deletions (T < n), showing that classical static balls-and-bins bounds carry over to the adaptive setting. The coupling reductions in Lemmas 3.3 and A.1 are clean and reusable. The 2-split analysis introduces an interesting hybrid argument with falsifiable bounds. The d=1 oblivious result (Theorem 5.1) and its random-forest equivalence provide a clean separation between adaptive and oblivious adversaries. The 2-split maximum load bound holding only with constant probability is honestly scoped. The extension to T > n/2 via the phase parameter ℓ in Theorems 3.1 and 3.5 adds generality beyond the headline result.

major comments (3)
  1. §4.2, Theorem 4.8 and Lemma 4.9: The maximum load bound for 2-split holds only with constant probability (1/2 per application of Lemma 4.9), yielding poly(log n) with constant probability overall. This is a genuine limitation of the d=2 guarantee, which the authors acknowledge. However, the gap between this constant-probability bound and the high-probability bounds achieved for d=1 (uniform) and two-choices is significant for the paper's central narrative that d=2 'suffices.' The authors should clarify whether this is an inherent barrier of the potential function technique or a fundamental limitation, and whether amplification via independent repetition is feasible in this setting.
  2. §4.1.1, proof of Lemma 4.3 (Claim 4.6): The argument that |T_t| ≤ O(log n) w.h.p. relies on stochastic domination by the uniform adaptive game (Theorem 3.1). However, in π_{t-1}, the Teflon balls from earlier rounds (T_1, ..., T_{t-1}) are thrown independently and uniformly, while normal balls are still split. The interaction between Teflon and normal balls could affect the load distribution in ways not captured by a direct domination argument over the uniform game. The authors should make the domination argument more explicit here, particularly regarding how the mixed Teflon/normal ball dynamics preserve the stochastic domination needed for the |T_t| bound.
  3. §4.1.2, proof of Lemma 4.4 (toy problem): The bound on the number of mini-games uses a geometric distribution with parameter p = 1 - O(k²/n), and the claim is that more than 20 mini-games occur with probability at most O(k²/n)^20. For k = O(log n), this gives O(log²n / n)^20 = n^{-10+o(1)}, which is sufficient for the stated 1/n^{10} bound. However, the constant in the O(k²/n) term is not tracked, and the exponent 20 appears to be chosen post hoc. The authors should verify that the implicit constant does not degrade the bound for the largest k = O(log n / log log n) allowed by the toy problem's hypothesis.
minor comments (7)
  1. §1, Theorem 1.3 is labeled '(Informal)' but Theorem 1.4 is not. For consistency, either both should be labeled informal or neither.
  2. §3, Theorem 3.1: The maximum load formula in the case ℓ ≥ log log n reads O(2^ℓ + log n · log log log n / log log n), but Remark 3.2 splits this into two sub-cases. The transition between these should be stated more carefully in the theorem statement itself.
  3. §4.1.1: The term 'Teflon balls' is informal. While it aids intuition, a brief formal definition alongside the informal name would improve readability for readers who may skip the technical overview.
  4. §5.2, Lemma 5.4: The coupling argument is correct but dense. A diagram illustrating the inductive construction (showing T_now, U_now, and P) would significantly aid comprehension.
  5. Appendix A, Lemma A.1: The invariant for the two-choices coupling uses L^na_i ≥ L^a_i (weak inequality) rather than equality as in Lemma 3.3. This difference is explained in the proof but should be highlighted in the lemma statement or a remark, as it affects the interpretation of the domination.
  6. §4.1.3, proof of Lemma 4.2: The reference to 'the same probability space as in the proof of Theorem 3.1' could benefit from a brief restatement of the coupling setup, as readers may not have the earlier proof immediately in mind.
  7. The paper uses both 'high probability' and explicit probability bounds (e.g., 1 - 1/n^7, 1 - 1/n^8) in different places. A brief remark standardizing the convention would help.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful reading and for recognizing the contributions of the paper. We address each major comment below.

read point-by-point responses

  1. Referee: §4.2, Theorem 4.8 and Lemma 4.9: The maximum load bound for 2-split holds only with constant probability (1/2 per application of Lemma 4.9), yielding poly(log n) with constant probability overall. The gap between this and the high-probability bounds for d=1 and two-choices is significant for the narrative that d=2 'suffices.' Clarify whether this is an inherent barrier of the potential function technique or a fundamental limitation, and whether amplification via independent repetition is feasible.

    Authors: We agree that the constant-probability bound warrants more discussion. To clarify the three sub-questions: (1) Whether this is an inherent barrier of the potential function technique or a fundamental limitation: we genuinely do not know. The potential function argument (Lemma 4.9) gives a 1/2 probability per application because it relies on Markov's inequality applied to the exponential potential w_t, and the bound E[w_{n/C}] <= e^{17}n is tight up to constants for our choice of alpha = 1/L. A high-probability bound would require a stronger concentration result for w_t, but the potential function evolves through adaptive choices by the adversary, making standard martingale concentration difficult to apply directly. We cannot rule out that a different technique (e.g., a layered induction argument adapted to the adaptive setting) could yield a high-probability bound, but we have not been able to carry this out. (2) Whether amplification via independent repetition is feasible: standard amplification (running multiple independent copies and taking the best) does not directly apply here, because the adversary is adaptive and can observe the outcomes of previous rounds. One cannot restart the game independently mid-stream. One could run multiple independent initializations and select the best before the game begins, but this only helps with the initial load, not the load accumulated during the game. (3) Regarding the narrative: we agree that the word 'suffices' in the introduction could be misread as claiming a high-probability bound. We will revise the introduction to state explicitly that the 2-split maximum load bound holds only with constant probability, and that closing the gap to high probability is left open. We believe the linear recourse bound (which does hold w.h.p. revision: partial

  2. Referee: §4.1.1, proof of Lemma 4.3 (Claim 4.6): The argument that |T_t| <= O(log n) w.h.p. relies on stochastic domination by the uniform adaptive game (Theorem 3.1). However, in pi_{t-1}, the Teflon balls from earlier rounds (T_1, ..., T_{t-1}) are thrown independently and uniformly, while normal balls are still split. The interaction between Teflon and normal balls could affect the load distribution in ways not captured by a direct domination argument over the uniform game. The authors should make the domination argument more explicit here.

    Authors: The referee raises a valid concern. The key observation is that in pi_{t-1}, the Teflon balls (from T_1, ..., T_{t-1}) are thrown independently and uniformly at random, while normal balls are split into two groups. The claim is that |T_t| (the number of normal balls in the deleted bin at round t) is stochastically dominated by the maximum load in the uniform adaptive game. The reason is as follows: the Teflon balls, being thrown independently and uniformly, are distributed exactly as in the uniform adaptive game. The normal balls, being split into two groups rather than thrown independently, can only increase the maximum load relative to the uniform game (splitting creates larger packets that can concentrate load). However, the referee is correct that the interaction between Teflon and normal balls is not fully spelled out: when a bin containing both Teflon and normal balls is deleted, the Teflon balls are thrown independently while the normal balls are split, and the resulting load distribution involves both. The stochastic domination argument needs to account for this mixed dynamics. The domination holds because the Teflon balls' independent uniform throws are stochastically dominated by the uniform game (they ARE the uniform game for those balls), and the normal balls' split throws produce loads that are stochastically dominated by independent uniform throws (since splitting into two groups can only increase maximum load compared to independent throws). Combining these, the total load is dominated by the uniform adaptive game. We agree this argument is currently too terse in the manuscript. We will expand the proof of Claim 4.6 to make the domination argument explicit, including a formal statement of how the mixed Teflon/normal dynamics preserve stochastic domination revision: yes

  3. Referee: §4.1.2, proof of Lemma 4.4 (toy problem): The bound on the number of mini-games uses a geometric distribution with parameter p = 1 - O(k^2/n), and the claim is that more than 20 mini-games occur with probability at most O(k^2/n)^20. For k = O(log n), this gives O(log^2 n / n)^20 = n^{-10+o(1)}, which is sufficient for the stated 1/n^{10} bound. However, the constant in the O(k^2/n) term is not tracked, and the exponent 20 appears to be chosen post hoc. The authors should verify that the implicit constant does not degrade the bound for the largest k = O(log n / log log n) allowed by the toy problem's hypothesis.

    Authors: The referee is correct that the implicit constant and the exponent 20 need to be tracked carefully. Let us verify the calculation. The collision probability per mini-game is at most C * k^2 / n for some explicit constant C, since there are at most O(k) rounds, each with collision probability at most 2k/(n/2) = 4k/n, giving a bound of O(k^2/n) with an explicit constant of, say, 4k * (4k/n) = 16k^2/n (being generous). The number of mini-games is dominated by a geometric with parameter p = 1 - 16k^2/n. The probability of more than 20 mini-games is at most (16k^2/n)^20. For the largest k allowed, which is k = c * log(n)/log log(n) for some constant c (from the hypothesis of Lemma 4.4, which requires k = O(log n)), we get (16c^2 log^2(n) / (n log^2 log(n)))^20. The numerator is log^2(n) / log^2 log(n) = n^{o(1)}, so the bound is n^{-20 + o(1)}, which is indeed at most n^{-10} for sufficiently large n. The exponent 20 was chosen to ensure a margin: even with the implicit constant 16 and the o(1) factor from k = O(log n / log log n), the bound remains n^{-10+o(1)} which is o(n^{-9}). We agree that the manuscript should make the constant explicit and verify the calculation for the largest k. We will revise the proof to track the constant explicitly and replace the post-hoc exponent 20 with a derivation showing the required exponent. revision: yes

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity. The central coupling arguments are new reductions to independently analyzable non-adaptive games, not self-citations or definitional equivalences.

full rationale

The paper's main results (Theorems 1.3, 3.1, 3.5) rest on coupling arguments (Lemmas 3.3, A.1) that reduce the adaptive game to a non-adaptive game with a specific stopping condition. The non-adaptive game's parameters (10n balls, subset-of-n/2^j stopping condition) are derived independently via Hoeffding's inequality (Lemma 3.4) and standard balls-into-bins results [RS98, BCSV00], not fitted to the target. The coupling invariant (L^na_i = L^a_i for uniform; L^na_i >= L^a_i for two choices) is a genuine stochastic domination argument, not a definitional equivalence. The 2-split analysis (Section 4) uses a toy problem (Lemma 4.4) analyzed from first principles via geometric random variables, and the pi_pay hybrid construction is a new reduction. The d=1 oblivious result (Theorem 5.1) uses a random-forest equivalence and Galton-Watson domination (Lemma 5.4) with independently computed parameters (Lemma 5.5). The only self-citation is Claim 5.2, which cites Lemma 5 of [FKS25] (shared authors Kaplan, Stemmer) for the geometric domination of per-ball recourse. This is a minor, non-load-bearing citation: it provides a convenient bound on individual ball recourse, but the main structural argument (forest equivalence, GW domination, tree-size bound) is self-contained in the present paper. The central claims do not reduce to any self-citation chain or fitted input. Score 2 reflects the minor self-citation that is not load-bearing for the paper's central theorems.

Assumptions & free parameters 2 free parameters · 7 assumptions · 3 invented entities

The paper introduces no new physical entities or axioms. The 'Teflon balls,' 'toy problem,' and 'π_pay game' are proof-theoretic constructs with well-defined rules and independently verified properties. The constants C and α are standard potential-function parameters, not fitted to data. The paper relies on standard concentration inequalities and classical balls-and-bins results as background.

free parameters (2)
  • C (constant in Lemma 4.9 / Theorem 4.8) = C > 2e^17 (sufficiently large constant)
    A universal constant chosen large enough for the potential function argument and Markov's inequality to work. Not fitted to data; chosen for the proof to close.
  • α (potential function parameter) = 1/L where L is the current maximum load
    Set to 1/L in the exponential potential w = Σ e^{αL_i}. This is a standard choice for potential-based load analysis, not a free parameter fitted to data.
assumptions (7)
  • standard math Hoeffding's inequality (Lemma 2.1)
    Standard concentration inequality used in Lemma 3.4 to bound the number of balls in the non-adaptive game.
  • standard math Bernstein's inequality (Lemma 2.2)
    Standard concentration inequality used in Lemma 5.7 to bound the total progeny of the Galton-Watson process.
  • standard math Azuma's inequality for submartingales (Theorem 4.12)
    Standard martingale concentration used in Theorem 4.8 to bound the number of phases before maximum load grows.
  • standard math McDiarmid's inequality (Lemma B.1)
    Standard bounded-differences inequality used in Appendix B to prove Lemma 4.7 (sum of L_i log L_i).
  • standard math Stochastic domination / monotone coupling (Lemma 1.7, Theorem 4.2.3 of [Roc24])
    Standard probability tool used throughout to reduce adaptive games to non-adaptive games via coupling.
  • domain assumption Classical balls-and-bins maximum load bounds [RS98, ABKU99, BCSV00]
    The paper uses known maximum load bounds for static balls-and-bins (O(log n / log log n) for uniform, O(log log n) for two choices) as black-box results applied to the non-adaptive game.
  • domain assumption Algorithm's random coins are hidden from the adversary (Remark 1.8)
    The paper explicitly states this is necessary for bounding the maximum load, and provides a counterexample showing that if coins are revealed, the adversary can force Ω(√n) load.
invented entities (3)
  • Teflon balls independent evidence
    purpose: Conceptual device in the hybrid game π_1 used to couple 2-split with π_pay. Teflon balls are thrown independently (not split) and can revert to normal balls when they become isolated.
    Not a new physical entity; it is a proof technique. The coupling is formally defined and the stochastic domination is proven. The 'Teflon' property is a bookkeeping mechanism for tracking which balls are thrown independently vs. split, with a well-defined reversion rule.
  • Toy problem (Section 4.1.2) independent evidence
    purpose: Simplified game to bound the recourse of k balls starting in one bin until they become isolated, used in Lemma 4.4.
    An auxiliary problem defined for analysis. Its recourse is bounded by O(k log k) via a geometric random variable argument, which is a self-contained derivation.
  • π_pay game independent evidence
    purpose: Intermediate game between 2-split and uniform: balls thrown independently but with extra O(k log k) cost per deletion of k balls.
    A proof construct. Its cost is shown to stochastically dominate 2-split recourse (Lemma 4.3) and to be O(n) with high probability (Lemma 4.2), both proven from first principles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Load Balancing under Adaptive Bin Deletions." pith.science (2026). https://pith.science/paper/UWTV4K7B

@misc{pith2026260706211,
  author       = {Pith},
  title        = {Pith review of: Load Balancing under Adaptive Bin Deletions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UWTV4K7B}},
  note         = {Machine review of arXiv:2607.06211}
}
abstract

We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with $n$ balls distributed across $n$ bins, the adversary deletes a bin in each step, forcing the algorithm to redistribute its balls to surviving bins. We prove that after $n/2$ rounds, uniform random redistribution yields optimal $O(n)$ recourse and $O(\frac{\log n}{\log \log n})$ maximum load. Furthermore, we show that applying the ``power of two choices'' reduces the maximum load to $O(\log \log n)$ while maintaining linear recourse. We also consider a variation of this game where the balls from the deleted bin are partitioned evenly among $d \ll n$ random bins rather than being redistributed independently. We demonstrate that keeping the balls together ($d=1$), which gives small maximum load and recourse against an oblivious adversary, fails against an adaptive adversary. Nevertheless, we show that splitting the balls into just two groups ($d=2$) is sufficient to recover linear recourse and efficient load balancing in the adaptive setting.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 59 canonical work pages

  1. [1]

    Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP) , series =

    Adi Fine and Haim Kaplan and Uri Stemmer , title =. Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP) , series =. 2025 , doi =

    work page 2025

  2. [2]

    30th Annual European Symposium on Algorithms (ESA 2022) , pages =

    Bhattacharya, Sayan and Saranurak, Thatchaphol and Sukprasert, Pattara , title =. 30th Annual European Symposium on Algorithms (ESA 2022) , pages =. 2022 , volume =

    work page 2022

  3. [3]

    Kane and Jelani Nelson and Ely Porat and David P

    Daniel M. Kane and Jelani Nelson and Ely Porat and David P. Woodruff , title =. Proceedings of the 43rd. 2011 , doi =

    work page 2011

  4. [4]

    Balanced allocations: the heavily loaded case , year =

    Berenbrink, Petra and Czumaj, Artur and Steger, Angelika and V\". Balanced allocations: the heavily loaded case , year =. doi:10.1145/335305.335411 , booktitle =

    work page doi:10.1145/335305.335411

  5. [5]

    Balanced Allocations: The Heavily Loaded Case , journal =

    Berenbrink, Petra and Czumaj, Artur and Steger, Angelika and V\". Balanced Allocations: The Heavily Loaded Case , journal =. 2006 , doi =

    work page 2006

  6. [6]

    and Karlin, Anna R

    Azar, Yossi and Broder, Andrei Z. and Karlin, Anna R. and Upfal, Eli , title =. SIAM Journal on Computing , volume =. 1999 , doi =

    work page 1999

  7. [7]

    Modern Discrete Probability: An Essential Toolkit , DOI=

    Roch, Sebastien , year=. Modern Discrete Probability: An Essential Toolkit , DOI=

    work page

  8. [8]

    Randomization and Approximation Techniques in Computer Science, 2nd International Workshop (RANDOM) , series =

    Martin Raab and Angelika Steger , title =. Randomization and Approximation Techniques in Computer Science, 2nd International Workshop (RANDOM) , series =. 1998 , doi =

    work page 1998

Show all 59 references
  1. [9]

    Dubhashi and Desh Ranjan , title =

    Devdatt P. Dubhashi and Desh Ranjan , title =. Random Struct. Algorithms , volume =

  2. [10]

    Bernoulli , volume=

    Bernstein-type exponential inequalities in survey sampling , author=. Bernoulli , volume=. 2019 , publisher=

    2019

  3. [11]

    2014 , issn =

    Balls into non-uniform bins , journal =. 2014 , issn =. doi:https://doi.org/10.1016/j.jpdc.2013.10.008 , author =

    2014 doi

  4. [12]

    2007 , isbn =

    Wieder, Udi , title =. 2007 , isbn =. doi:10.1145/1248377.1248407 , booktitle =

    2007 doi

  5. [13]

    Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA) , pages =

    Kenthapadi, Krishnaram and Panigrahy, Rina , title =. Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA) , pages =. 2006 , isbn =

    2006

  6. [14]

    Brighten , title =

    Godfrey, P. Brighten , title =. 2008 , booktitle =

    2008

  7. [15]

    2008 , issn =

    On weighted balls-into-bins games , journal =. 2008 , issn =. doi:https://doi.org/10.1016/j.tcs.2008.09.023 , author =

    2008 doi

  8. [16]

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

    Peres, Yuval and Talwar, Kunal and Wieder, Udi , title =. Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages =. 2010 , isbn =

    2010

  9. [17]

    1997 , isbn =

    Karger, David and Lehman, Eric and Leighton, Tom and Panigrahy, Rina and Levine, Matthew and Lewin, Daniel , title =. 1997 , isbn =. doi:10.1145/258533.258660 , booktitle =

    1997 doi

  10. [18]

    and Morris, R

    Stoica, I. and Morris, R. and Liben-Nowell, D. and Karger, D.R. and Kaashoek, M.F. and Dabek, F. and Balakrishnan, H. , journal=. Chord: a scalable peer-to-peer lookup protocol for Internet applications , year=

  11. [19]

    Load balancing with dynamic set of balls and bins , year =

    Aamand, Anders and Knudsen, Jakob B. Load balancing with dynamic set of balls and bins , year =. doi:10.1145/3406325.3451107 , booktitle =

    doi

  12. [20]

    2017 , issue_date =

    Wieder, Udi , title =. 2017 , issue_date =. doi:10.1561/0400000070 , journal =

    2017 doi

  13. [21]

    2022 , volume =

    Bansal, Nikhil and Kuszmaul, William , booktitle =. 2022 , volume =

    2022

  14. [22]

    1994 , issn =

    On-line load balancing , journal =. 1994 , issn =. doi:https://doi.org/10.1016/0304-3975(94)90153-8 , author =

    1994 doi

  15. [23]

    A Framework for Adversarially Robust Streaming Algorithms , journal =

    Omri Ben. A Framework for Adversarially Robust Streaming Algorithms , journal =. 2022 , doi =

    2022

  16. [24]

    Avinatan Hassidim and Haim Kaplan and Yishay Mansour and Yossi Matias and Uri Stemmer , title =. J. 2022 , doi =

    2022

  17. [25]

    Adversarial laws of large numbers and optimal regret in online classification , booktitle =

    Noga Alon and Omri Ben. Adversarial laws of large numbers and optimal regret in online classification , booktitle =. 2021 , doi =

    2021

  18. [26]

    Advances in Cryptology -

    Haim Kaplan and Yishay Mansour and Kobbi Nissim and Uri Stemmer , title =. Advances in Cryptology -. 2021 , doi =

    2021

  19. [27]

    Woodruff and Samson Zhou , title =

    David P. Woodruff and Samson Zhou , title =. 62nd. 2021 , doi =

    2021

  20. [28]

    Adversarially Robust Streaming via Dense-Sparse Trade-offs , booktitle =

    Omri Ben. Adversarially Robust Streaming via Dense-Sparse Trade-offs , booktitle =. 2022 , doi =

    2022

  21. [29]

    13th Innovations in Theoretical Computer Science Conference, (ITCS) , series =

    Amit Chakrabarti and Prantar Ghosh and Manuel Stoeckl , title =. 13th Innovations in Theoretical Computer Science Conference, (ITCS) , series =. 2022 , doi =

    2022

  22. [30]

    Proceedings of the 42nd

    Sepehr Assadi and Amit Chakrabarti and Prantar Ghosh and Manuel Stoeckl , title =. Proceedings of the 42nd. 2023 , doi =

    2023

  23. [31]

    Algorithmica , volume =

    Idan Attias and Edith Cohen and Moshe Shechner and Uri Stemmer , title =. Algorithmica , volume =. 2024 , doi =

    2024

  24. [32]

    Woodruff and Samson Zhou , title =

    David P. Woodruff and Samson Zhou , title =. Advances in Neural Information Processing Systems. 2024 , url =

    2024

  25. [33]

    Proceedings of the 2023

    Manuel Stoeckl , title =. Proceedings of the 2023. 2023 , doi =

    2023

  26. [34]

    39th Computational Complexity Conference,

    Amit Chakrabarti and Manuel Stoeckl , title =. 39th Computational Complexity Conference,. 2024 , doi =

    2024

  27. [35]

    Proceedings of the 41st International Conference on Machine Learning , articleno =

    Ahmadian, Sara and Cohen, Edith , title =. Proceedings of the 41st International Conference on Machine Learning , articleno =. 2024 , publisher =

    2024

  28. [36]

    On the Robustness of

    Cohen, Edith and Lyu, Xin and Nelson, Jelani and Sarlos, Tamas and Shechner, Moshe and Stemmer, Uri , booktitle =. On the Robustness of. 2022 , volume =

    2022

  29. [37]

    Tricking the hashing trick: a tight lower bound on the robustness of CountSketch to adaptive inputs , year =

    Cohen, Edith and Nelson, Jelani and Sarl\'. Tricking the hashing trick: a tight lower bound on the robustness of CountSketch to adaptive inputs , year =. doi:10.1609/aaai.v37i6.25882 , booktitle =

    doi

  30. [38]

    and Yu, Huacheng and Zhou, Samson , booktitle=

    Gribelyuk, Elena and Lin, Honghao and Woodruff, David P. and Yu, Huacheng and Zhou, Samson , booktitle=. A Strong Separation for Adversarially Robust _0 Estimation for Linear Sketches , year=

  31. [39]

    , title =

    Hardt, Moritz and Woodruff, David P. , title =. 2013 , isbn =. doi:10.1145/2488608.2488624 , booktitle =

    2013 doi

  32. [40]

    and Yu, Huacheng and Zhou, Samson , title =

    Gribelyuk, Elena and Lin, Honghao and Woodruff, David P. and Yu, Huacheng and Zhou, Samson , title =. 2025 , isbn =. doi:10.1145/3717823.3718227 , booktitle =

    2025 doi

  33. [41]

    2025 , eprint=

    One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches , author=. 2025 , eprint=

    2025

  34. [42]

    2025 , eprint=

    The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for _2 Norm Estimation , author=. 2025 , eprint=

    2025

  35. [43]

    Bender and Jake Christensen and Alex Conway and Martin Farach-Colton and Rob Johnson and Meng-Tsung Tsai , title =

    Michael A. Bender and Jake Christensen and Alex Conway and Martin Farach-Colton and Rob Johnson and Meng-Tsung Tsai , title =. Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2019 , pages =

    2019

  36. [44]

    Michael Mitzenmacher and Eli Upfal , title =

  37. [45]

    Gonnet , title =

    Gaston H. Gonnet , title =. J

  38. [46]

    HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm , booktitle =

    Philippe Flajolet and. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm , booktitle =. 2007 , publisher =

    2007

  39. [47]

    Proceedings of the 26th annual international conference on machine learning (ICML) , pages=

    Feature hashing for large scale multitask learning , author=. Proceedings of the 26th annual international conference on machine learning (ICML) , pages=

  40. [48]

    International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM) , pages=

    On balls and bins with deletions , author=. International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM) , pages=

  41. [49]

    Journal of the ACM (JACM) , volume=

    How asymmetry helps load balancing , author=. Journal of the ACM (JACM) , volume=. 2003 , publisher=

    2003

  42. [50]

    The 13th Innovations in Theoretical Computer Science (ITCS) , series =

    Dimitrios Los and Thomas Sauerwald , title =. The 13th Innovations in Theoretical Computer Science (ITCS) , series =

  43. [51]

    SIAM journal on Applied Mathematics , volume=

    Bounds on multiprocessing timing anomalies , author=. SIAM journal on Applied Mathematics , volume=. 1969 , publisher=

    1969

  44. [52]

    Mathematical programming , volume=

    Approximation algorithms for scheduling unrelated parallel machines , author=. Mathematical programming , volume=. 1990 , publisher=

    1990

  45. [53]

    Journal of the ACM (JACM) , volume=

    Using dual approximation algorithms for scheduling problems theoretical and practical results , author=. Journal of the ACM (JACM) , volume=. 1987 , publisher=

    1987

  46. [54]

    Distributed Comput

    Luca Becchetti and Andrea Clementi and Emanuele Natale and Francesco Pasquale and Gustavo Posta , title =. Distributed Comput. , volume =. 2019 , doi =

    2019

  47. [55]

    and Peng, Richard and Sidford, Aaron , title =

    van den Brand, Jan and Gao, Yu and Jambulapati, Arun and Lee, Yin Tat and Liu, Yang P. and Peng, Richard and Sidford, Aaron , title =. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2022 , isbn =. doi:10.1145/3519935.3520068 , abstract =

    2022 doi

  48. [56]

    54th Annual

    Amos Beimel and Haim Kaplan and Yishay Mansour and Kobbi Nissim and Thatchaphol Saranurak and Uri Stemmer , title =. 54th Annual. 2022 , doi =

    2022

  49. [57]

    49th International Colloquium on Automata, Languages, and Programming,

    Aaron Bernstein and Jan van den Brand and Maximilian Probst Gutenberg and Danupon Nanongkai and Thatchaphol Saranurak and Aaron Sidford and He Sun , title =. 49th International Colloquium on Automata, Languages, and Programming,. 2022 , doi =

    2022

  50. [58]

    17th Innovations in Theoretical Computer Science Conference,

    Bernhard Haeupler and Marc Kaufmann and Raghu Raman Ravi and Ulysse Schaller , title =. 17th Innovations in Theoretical Computer Science Conference,. 2026 , doi =

    2026

  51. [59]

    The Adversarial Robustness of Sampling , booktitle =

    Omri Ben. The Adversarial Robustness of Sampling , booktitle =. 2020 , doi =

    2020

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.