{"id":"194c2b8f-417f-48c6-89ce-e731b5a31c9d","arxiv_id":"2607.06211","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":2,"one_line_summary":"In an adaptive bin-deletion game, uniform redistribution and two-choice yield optimal O(n) recourse and O(log log n) load after n/2 rounds, and 2-splitting suffices for linear recourse.","lead":"This paper analyzes a balls-and-bins load balancing game where an adaptive adversary deletes bins one at a time, forcing the algorithm to redistribute balls. It proves that uniform random redistribution and power-of-two-choices maintain optimal load and linear recourse after n/2 deletions, and that splitting deleted-bin balls into just two groups suffices against adaptive adversaries.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The coupling arguments in Lemmas 3.3 and A.1 are sound, and the 2-split analysis is honestly scoped with its constant-probability limitation clearly stated.","rationale":"The reader correctly identified that the coupling argument in Lemma 3.3 is the load-bearing element and that it holds. The reader also correctly noted the limitations: the 2-split maximum load bound holds only with constant probability (Theorem 4.8), and extension to T > n/2 remains open. These are honestly stated in the paper and do not undermine the core contributions. I independently verified the coupling arguments, the stopping-condition logic, the invariant maintenance in both the uniform and two-choices cases, the 2-split recourse hybrid argument, and the d=1 oblivious analysis. No internal inconsistency or hidden assumption that would compromise the central claims was found. The proofs are detailed and verifiable. The ACCEPT verdict with HIGH confidence is appropriate.","tokens_in":23846,"tokens_out":786,"duration_ms":1357812,"concrete_test":"Verify the invariant in Lemma A.1 (two-choices coupling) under an adversarial sequence where the adversary consistently deletes the bin with the highest load differential between the adaptive and non-adaptive games. Specifically, simulate the coupling for small n (e.g., n=64, phase j=1) and check that L^na_i >= L^a_i holds for all surviving bins i at every step, including the edge case where L^a_i < L^a_{i'} but L^na_i >= L^na_{i'} (the ball goes to different bins in the two games). If the invariant is violated in any step, the coupling argument for the two-choices case would need revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.3) rests on the coupling in Lemma 3.3 (uniform) and Lemma A.1 (two choices), which reduce the adaptive game to a non-adaptive game with a stopping condition on subsets of surviving bins. I checked the key step: right before the n/2^j-th deletion, there are n/2^j + 1 surviving bins containing at most n balls total, so some subset of n/2^j bins has strictly fewer than n balls, meaning the non-adaptive game has not yet terminated. This is correct. The invariant L^na_i >= L^a_i is maintained correctly in both the uniform case (Lemma 3.3) and the two-choices case (Lemma A.1), where the two-choices invariant requires the additional argument that if L^a_i < L^a_{i'} but L^na_i >= L^na_{i'}, then L^a_i <= L^na_i - 1 (integer loads), preserving the invariant after incrementing. The recourse bound O(n) follows from Lemma 3.4 (at most 10n balls thrown w.h.p.) and the maximum load from standard balls-into-bins results with 10n balls. The 2-split recourse argument (Lemma 4.3) uses a hybrid/Teflon-ball construction with a toy problem (Lemma 4.4) bounding the cost of isolating k balls at O(k log k); the geometric distribution argument for the number of mini-games is sound for k = O(log n). The 2-split maximum load (Theorem 4.8) holds only with constant probability, which is honestly stated. The d=1 oblivious result (Theorem 5.1) uses a clean random-forest equivalence and a Galton-Watson domination argument. I do not find a load-bearing concern that would undermine the central claims.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","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.","tokens_in":24165,"tokens_out":1501,"duration_ms":324764,"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":[{"comment":"§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.","section":null},{"comment":"§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.","section":null},{"comment":"§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.","section":null}],"minor_comments":[{"comment":"§1, Theorem 1.3 is labeled '(Informal)' but Theorem 1.4 is not. For consistency, either both should be labeled informal or neither.","section":null},{"comment":"§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.","section":null},{"comment":"§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.","section":null},{"comment":"§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.","section":null},{"comment":"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.","section":null},{"comment":"§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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper shares authors with FKS25, but the present results constitute a genuine extension (partial deletions, d-split analysis) rather than a circular restatement. The coupling to non-adaptive games is a new reduction with independently derived parameters. The 2-split maximum load bound at constant probability is the weakest part of the paper, but it is honestly scoped and the recourse bound (which is arguably the more important quantity) holds with high probability. I recommend minor revision: the major comments above are requests for clarification and verification rather than indications of errors in the central claims."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful reading and for recognizing the contributions of the paper. We address each major comment below.","responses":[{"response":"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_made":"partial","referee_comment":"§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."},{"response":"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_made":"yes","referee_comment":"§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."},{"response":"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_made":"yes","referee_comment":"§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."}],"tokens_in":23743,"tokens_out":1591,"duration_ms":322794,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"This paper resolves the open question from FKS25 about what happens when the adaptive bin-deletion game runs for only T < n rounds instead of T = n-1. The main result (Theorem 1.3) shows that for T = n/2, uniform redistribution gives O(n) recourse and O(log n / log log n) max load, and two choices gives O(n) recourse and O(log log n) max load — both matching classical static bounds. This is a clean and correct result. The coupling in Lemma 3.3 reducing the adaptive game to a non-adaptive one is the key technical contribution, and it works: the invariant L^na_i = L^a_i is maintained, and the stopping-condition argument (right before the n/2^j-th deletion, n/2^j + 1 surviving bins contain at most n balls, so some subset of n/2^j bins has fewer than n) is correct. The two-choices extension in Lemma A.1 handles the subtlety that loads can cross under coupling, using the integer-load argument. The phase-based analysis extending to general T is straightforward and well-structured. The d=1 oblivious result (Theorem 5.1) via the random-forest/Galton-Watson domination is a nice bonus — it gives a clean separation between adaptive and oblivious adversaries. The 2-split recourse argument (Section 4.1) is the most technically involved part. The Teflon-ball hybrid argument and the toy problem (Lemma 4.4) are genuinely new, and the reduction to π_pay is sound. The recourse bound of O(n) w.h.p. holds up. The soft spot is the 2-split maximum load (Theorem 4.8): it holds only with constant probability, not high probability. The potential-function argument in Lemma 4.9 gives that each log n-factor increase in max load requires Ω(n) rounds with probability 1/2, and the submartingale/Azuma argument then gives poly(log n) load with constant probability. This is honestly stated but is a real limitation — the bound is not w.h.p., and extending to T > n/2 remains open. The free parameters C and α are standard constants that do not undermine the argument. No circularity with FKS25: the coupling is a new reduction, and the non-adaptive game parameters are derived independently. This paper is for researchers in randomized algorithms and dynamic data structures. The core results (Theorems 1.3, 3.1, 3.5, 5.1) are solid and deserve a serious referee. The 2-split max-load bound is the weakest part but does not undermine the main contributions.","headline":"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.","tokens_in":24704,"tokens_out":655,"would_cite":true,"duration_ms":129902,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Classical load-balancing bounds survive adaptive bin deletions","keywords":["balls and bins","load balancing","adaptive adversary","power of two choices","stochastic domination","coupling argument","bin deletion","recourse"],"falsifier":"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.","tokens_in":23916,"feed_emoji":"","tokens_out":1182,"duration_ms":190887,"temperature":0.7,"pith_summary":"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.","feed_headline":"","feed_subtitle":"","key_machinery":"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.","core_discovery":"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负载都","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Two choices hold load steady under adaptive bin deletions","Adaptive adversary deletes bins; power of two choices still works","Bin deletion game: two-way splitting beats single-bin redistribution","Coupling tames adaptive bin deletions in balls-and-bins load balancing","Two groups suffice when an adaptive adversary deletes bins"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Two choices hold load steady under adaptive bin deletions","Adaptive adversary deletes bins; power of two choices still works","Bin deletion game: two-way splitting beats single-bin redistribution","Coupling tames adaptive bin deletions in balls-and-bins load balancing","Two groups suffice when an adaptive adversary deletes bins","Random redistribution under adaptive bin deletion stays near-optimal","Linear recourse survives adaptive bin deletion with two choices","Adaptive deletions break single-bin redistribution but not two-way splits","Non-adaptive coupling bounds recourse in adaptive bin-deletion game","Splitting into two groups recovers load balance against adaptive deletion"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":815,"prompt_tokens":476,"completion_tokens":339,"prompt_tokens_details":null},"tokens_in":476,"tokens_out":339,"duration_ms":28239,"temperature":1.0,"reasoning_tokens":232,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T13:08:17.497589+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"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.","supporting_citations":[],"review_version":1}