{"id":"567dd884-4014-4042-8aed-1a0db3bf9dd5","arxiv_id":"2607.20727","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":4,"one_line_summary":"Under the new 'edit-neighboring' privacy definition, private continual counting is possible with only polylogarithmic error, while every additive-noise counter provably needs polynomial error.","lead":"This paper defines a stricter privacy notion for streams where one person joining can push all later data one step later in time, and shows that private counting still matches standard guarantees with small polylogarithmic error. It also proves that every standard noise-adding counter must suffer polynomial error under this notion, and that a broader adjacency notion makes sub-polynomial error impossible.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound results depend on Lemma 7.5, cited without proof to a concurrent first-author paper; if that lemma fails, Theorems 1.2 and 1.5 collapse.","rationale":"The reader identified the same weakest assumption: the lower-bound half rests on external results, especially Lemma 7.5. I agree that this is the most load-bearing concern in the paper. The upper-bound mechanisms (SimECC/ECC) appear internally consistent; spot-checks of the budget accounting, the coupling in Lemma 4.15, and the accuracy proofs are plausible, and the SVT-based privacy proof is dense but not obviously flawed. The lower-bound contribution, however, is a central part of the paper's contribution (it motivates why randomized data-dependent checkpoints are necessary), and it hinges on a single unproved, imported lemma from concurrent work by the first author. Because the lemma is concrete and falsifiable, a brute-force search over small instances is a decisive test. If the lemma fails, the lower-bound theorems collapse; if it passes, the main lower-bound argument is supported, but a formal proof should ideally be included to make the paper self-contained. Therefore, I recommend conditional acceptance pending verification of Lemma 7.5, which is a modest and concrete condition.","tokens_in":70871,"tokens_out":22130,"duration_ms":153903,"concrete_test":"Write a brute-force verifier for Lemma 7.5: enumerate all pairs (σ,σ′) of item-level neighboring CountDistinct streams of length T ≤ 8 over a small universe (e.g., |U|=2), compute d(σ) − d(σ′), and check whether every interval sum lies in {−1,0,1} (equivalently, whether the prefix-sum difference is always in {0,1} or always in {0,−1}). If any violation is found, Lemma 7.5 is false and Theorems 1.2/1.5 are invalidated. If no violation is found, the lemma gains strong empirical support; the paper should still be expected to provide a self-contained proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The lower bounds for edit-neighboring streams (Theorem 1.2 / Theorem 7.14) and for prefix-sum neighboring streams (Theorem 1.5) are derived through Claim 7.4, which converts CountDistinct hardness into prefix-sum-neighbor hardness. The pivotal step is Lemma 7.5, attributed to Andersson et al. (2026), a concurrent paper by the first author. Lemma 7.5 asserts that for item-level neighboring CountDistinct streams, the difference of their difference streams, d(σ) − d(σ′), lies in S1 = {v : every interval sum of v has absolute value ≤ 1}. The proof of Claim 7.4 uses exactly this S1 condition: it argues that if some prefix of v were 1 and another prefix were −1, an interval sum of 2 would arise, contradicting S1, and hence the prefix-sum difference stays in {0,1} or {0,−1}. Lemma 7.5 is stated without proof in this manuscript, so the entire lower-bound chain is only as strong as an external citation. If the lemma is false, or if the neighboring definition in Andersson et al. differs subtly from Definition 7.2, Claim 7.4 fails and the lower bounds for both edit-neighboring and prefix-sum neighboring streams are unsupported. The paper provides no internal derivation or independent evidence for Lemma 7.5, making this the least secure link in the lower-bound half.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new adjacency notion for differential privacy under continual observation, called edit-neighboring streams, where one neighboring stream is obtained by inserting a value and shifting subsequent entries until the first ⊥ (or the end of the stream). The main claims are: (1) a lower bound showing that every data-independent additive-noise mechanism for edit-neighboring continual counting must incur polynomial ℓ∞ error; (2) upper-bound mechanisms SimECC and ECC, built from standard swap-neighboring continual counters as black boxes, that achieve the same polylogarithmic error as the standard setting, with ECC additionally being sparsity-adaptive; (3) a general lower bound for the more permissive prefix-sum-neighboring relation; and (4) synthetic experiments illustrating a practical separation. The formal results are Theorem 4.8/6.3 and Theorem 4.3/6.5 on the upper-bound side, and Theorems 1.2, 1.5, 7.6, 7.8, and 7.14 on the lower-bound side.","tokens_in":71110,"tokens_out":15543,"duration_ms":118133,"significance":"If the results are correct, the paper delivers a clean and nontrivial message: hiding participation shifts under continual observation need not cost asymptotic accuracy relative to the standard swap-neighboring model, but it does force a departure from input-independent noise to randomized, privately scheduled checkpoints. The upper-bound half is a genuine strength: the mechanisms are fully specified, all constants are fixed analytically (thresholds, privacy splits, noise scales), and the privacy/accuracy proofs are detailed and largely self-contained. The experimental section is honest, includes code, and explicitly states that the attack is a single natural attack rather than a claim of unconditional robustness. The lower-bound half is elegant and uses a sensitivity-set-containment framework that cleanly separates the edit-neighboring and prefix-sum-neighboring settings. However, the lower-bound chain depends on a pivotal lemma that is cited without proof, which is a load-bearing gap in the current manuscript.","major_comments":[{"comment":"The lower bounds for Count(∼p,{-1,0,1}^T), Count(∼p,{0,1}^T), and consequently Theorems 1.2, 1.5, 7.6, 7.8 and 7.14 all hinge on Lemma 7.5, which asserts that for item-level neighboring CountDistinct streams, d(σ)-d(σ′) ∈ S1. This lemma is stated without proof and attributed to Andersson et al. (2026), a concurrent paper sharing a first author. Claim 7.4 is only a derivation from the S1 property; the S1 assertion is the actual content. If Lemma 7.5 is false, or if its neighboring definition differs from Definition 7.2 in a way that invalidates the transfer, the entire lower-bound half collapses. Please either include a self-contained proof of Lemma 7.5 in an appendix, or explicitly state the lower-bound theorems as conditional on this external result. As written, this is the single most important unresolved point in the paper.","section":"§7.1, Lemma 7.5"}],"minor_comments":[{"comment":"The proof of part (ii) appears to yield a factor of e^ε rather than the stated e^{2ε}: two DLap shifts each give e^{ε/2}. Since e^ε ≤ e^{2ε}, the statement remains true, but the displayed derivation and the final bound should be aligned to avoid confusion.","section":"§6, Lemma 6.2"},{"comment":"The informal theorems promise failure probability δ for all t, while the formal accuracy theorems condition on three separate events (EPart, CC accuracy, BCC accuracy). Please make the total failure-probability budget explicit, i.e., state how β, β_C, and β_B are chosen so that the union bound gives exactly the advertised 1−δ.","section":"Theorems 1.3/1.4 vs. Theorems 4.3/6.5"},{"comment":"The notation ECC is used both for the mechanism and for the error function of the underlying standard continual counter. This is confusing in the technical overview; consider renaming the error function (e.g., E_std).","section":"§2"},{"comment":"In item 2, the definition of s_t as ∑_{i≤t} x_i omits the index bound; it should say s_t = ∑_{i=1}^t x_i with ⊥ treated as 0, and it is useful to set s_0 = 0.","section":"Definition 4.1"},{"comment":"The row for SimECC reports the same RMSE for Adv≤0.1 and Adv≤0.05. This is plausible because the attack advantage is already near zero at the smallest error setting, but the caption or text should state this explicitly so readers do not infer a typo.","section":"§8, Table 1"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound half of the paper is solid and would be a strong contribution on its own. The main risk for this submission is the lower-bound half: Lemma 7.5 is pivotal, unproved, and cited to a concurrent paper by the first author. I recommend asking the authors to include a complete proof of Lemma 7.5 in the appendix or to make the lower-bound theorems explicitly conditional. The overlap with the independent concurrent work by Chan et al. (2026) is discussed fairly, but the editor may wish to verify that the attribution of Lemma 7.5 is settled before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is a strong theory paper that introduces a new adjacency relation for continual observation—edit-neighboring streams—and shows the first mechanisms with polylog additive error under it. Second, the upper bounds (SimECC/ECC) are self-contained and check out; the lower bounds rest on one external lemma, Lemma 7.5, cited without proof to a concurrent first-author paper, and that is the one place I'd want a referee to dig.\n\nWhat's new: the edit-neighboring definition (insertion shifts the stream until a ⊥ absorbs the cascade), the SimECC and ECC mechanisms with polylog error matching the standard swap-neighboring setting up to constants, and the lower bounds for data-independent additive-noise mechanisms (Ω̃(T^{1/3})) and for prefix-sum neighboring streams (polynomial error for any mechanism). The paper is careful with the model: it states the semantics, flags in §1.2 that finer time discretization could sidestep shifts, and is honest that the experiments are a toy model with a single attack.\n\nCredit where due: I spot-checked the heavy accounting—the Laplace-shift coupling in Lemma 4.15, the privacy-budget split in Theorem 4.8 (17ε_p/3 + 4ε_C + 2ε_B = ε), the checkpoint-counting in Lemma 4.4, the TritsToBits case analysis, and the sensitivity-set argument in Lemma 7.13—and it is consistent. The heavy SVT coupling in Lemma 4.14/Appendix B is dense; I couldn't fully re-derive every line, but I didn't find a red flag.\n\nThe real soft spot is Lemma 7.5. It asserts that item-level neighboring CountDistinct streams have difference streams whose interval sums are bounded by 1, and that is the hinge converting CountDistinct hardness into prefix-sum-neighbor hardness. The lemma is cited to Andersson et al. (2026) with no proof here, and Theorems 1.2 and 1.5 collapse if it fails. This is not a fatal flaw, but it is a real dependency. A referee should be asked to verify that lemma, or the paper should include a proof.\n\nWho this is for: anyone working on DP under continual observation, especially on privacy definitions and lower bounds. It deserves a serious referee. I'd send it to review with the explicit instruction to check Lemma 7.5.","headline":"Strong paper introducing edit-neighboring streams with polylog-error mechanisms; the lower bounds hinge on an unproven external lemma that a referee should verify.","tokens_in":71816,"tokens_out":2729,"would_cite":true,"duration_ms":23320,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Edit-neighboring data streams still admit polylogarithmic-error private counting.","keywords":["differential privacy","continual observation","edit-neighboring streams","continual counting","factorization mechanism","sparse vector technique","prefix-sum neighbors","lower bounds"],"falsifier":"A concrete check: build a data-independent additive-noise mechanism for {0,1,⊥}T that achieves sub-polynomial ℓ∞ error while satisfying (ε,δ)-DP for edit neighbors; or, alternatively, exhibit a specific pair of item-level neighboring CountDistinct streams whose difference streams violate the S1 condition of Lemma 7.5. Either would expose a gap in the lower-bound chain.","tokens_in":70604,"feed_emoji":"🔒","tokens_out":3714,"duration_ms":31569,"temperature":0.7,"pith_summary":"This paper asks what happens to differential privacy under continual observation when an individual's decision to participate can shift an entire data stream by one time-step, possibly causing a cascade of downstream shifts until an empty slot (⊥) absorbs the queue. It proves that every data-independent additive-noise mechanism—including the standard factorization counters—must incur polynomial error Ω̃(min{T^{1/3}/ε^{2/3}, T}) (or Ω(√T/ε) with pure DP) on such edit-neighboring streams. It then constructs the first mechanisms, SimECC and ECC, that achieve the same polylogarithmic additive error as the standard swap-neighboring setting, with only modestly worse constants, and a sparsity-adaptive version whose error depends on the number of non-⊥ values. A companion lower bound shows that an even more general notion—prefix-sum neighboring streams—cannot escape polynomial error for arbitrary mechanisms. Experiments on structured Bernoulli streams show the separation already appears at stream length 10^4.","feed_headline":"One shifted entry does not break private stream counting","feed_subtitle":"New randomized-checkpoint counters match standard privacy accuracy; input-independent noise provably cannot.","key_machinery":"The central object is the randomized checkpoint/bucket schedule: bucket sizes are drawn from a discrete Laplace distribution, so that an insertion shifts only a constant number of bucket sums under a coupling that matches checkpoints between neighboring streams. Around this, the mechanism layers a standard continual counter on the bucket sums and a 'biased' continual counter (which never underestimates) to release noisy checkpoints, so the randomization that absorbs the shift is hidden. On the lower-bound side, the hinge is the reduction from CountDistinct: difference streams of item-level neighboring cardinality streams are prefix-sum neighbors, so known CountDistinct hardness transfers.","core_discovery":"The paper's central claim is that participation-shift privacy (edit-neighboring DP) does not cost asymptotic accuracy: one can recover the standard swap-neighboring error bound O((1/ε) ln t √(ln(t/δ) ln(1/δ))) for continual counting. The catch is that this requires abandoning input-independent noise; any mechanism that adds noise to the prefix sums without looking at the input must pay polynomial error. The construction achieves the match by randomizing the checkpoints at which the counter updates, coupling those checkpoints across neighboring streams, and using a biased continual counter to schedule releases.","pith_inferences":["The paper's shift-until-⊥ semantics are a modeling choice: if real systems can resolve collisions by fine-grained time discretization instead of shifting, the privacy threat largely dissolves—at an accuracy cost that the paper itself flags in §1.2. A testable extension is to quantify that accuracy cost for realistic arrival processes.","The lower bound inherits its force from two imported results (Jain et al. 2023a and a lemma attributed to Andersson et al. 2026). If that second lemma—that distinct-count difference streams lie in S1—fails for some adversarial stream family, both lower-bound theorems would need re-examination.","Because the lower bound applies only to data-independent mechanisms, the paper indirectly predicts that any near-optimal edit-private counter must make its noise depend on the input; a natural next step is to see whether input-dependent noise also helps in the standard swap model.","The empirical attack (a linear statistic over a known rate profile) is only one adversary; the authors themselves call it a 'simple' attack. A harder test would be a Bayesian or adaptive adversary that searches the output space—the gap between swap-private and edit-private counters under such an adversary is open."],"forward_implications":["Edit-neighboring DP is strictly stronger than swap-neighboring DP yet achieves the same order of additive error for continual counting; the price is only larger constants.","Any factorization-style, data-independent continual counter—the state of the art for the standard model—cannot be reused 'as is' for edit-neighboring streams; it must be randomized in an input-dependent way.","The sparsity-adaptive variant ECC shows that in sparse streams the leading error term depends only on the number of real values, not on the total time horizon T.","The prefix-sum-neighboring lower bound shows that reductions that map problems such as distinct-counting onto continual counting cannot escape polynomial error for arbitrary mechanisms."],"fun_headline_variants":["Edit-neighboring privacy: polylog error possible, but not with additive noise","Shifted participation doesn't hurt accuracy if you adapt noise","Edit-neighboring streams: polylog error with adaptive noise, not additive","Polylog error for shift-privacy only if noise is input-dependent","Edit-neighboring DP: match standard error, but only with adaptive noise"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire result depends on the model in which a participation collision causes a cascade of shifts until the first empty slot (⊥), with a fixed horizon T discarding the last value; if real systems can instead absorb collisions by fine-grained time discretization, the problem—and both the lower and upper bounds—change.","fun_headline_variants_meta":{"raw":{"variants":["Edit-neighboring privacy: polylog error possible, but not with additive noise","Shifted participation doesn't hurt accuracy if you adapt noise","Edit-neighboring streams: polylog error with adaptive noise, not additive","Polylog error for shift-privacy only if noise is input-dependent","Edit-neighboring DP: match standard error, but only with adaptive noise"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000734,"raw_usage":{"total_tokens":3171,"prompt_tokens":847,"completion_tokens":2324,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":2225}},"tokens_in":591,"tokens_out":2324,"duration_ms":15133,"temperature":1.0,"reasoning_tokens":2225,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T09:34:38.393997+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: build a data-independent additive-noise mechanism for {0,1,⊥}T that achieves sub-polynomial ℓ∞ error while satisfying (ε,δ)-DP for edit neighbors; or, alternatively, exhibit a specific pair of item-level neighboring CountDistinct streams whose difference streams violate the S1 condition of Lemma 7.5. Either would expose a gap in the lower-bound chain.","supporting_citations":[],"review_version":1}