{"id":"1b031c4c-40e8-437a-b80d-7030a9ac3285","arxiv_id":"2611.17083","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New competitive algorithms for list update with time windows and delays, without batch serving, give 3-competitive deterministic and randomized constant-factor guarantees.","lead":"This paper introduces a no-batching-allowed model for list update with time windows and delays, where every request must be served by a separate access. It provides tight deterministic and randomized competitive ratios, showing that the new model admits better algorithmic guarantees than the batch-serving counterpart.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"WBIT's 7/4-competitive guarantee for all 2-overlap inputs relies on Lemma 4.4, whose transformation may alter OPT's schedule in a way that invalidates the potential-function analysis.","rationale":"The reader's weakest_assumption correctly identifies that the WBIT guarantee for general k depends on the no-self-overlap assumption, and that for k=2 this assumption is removed via Lemma 4.4. However, the reader does not identify a specific load-bearing concern with Lemma 4.4 itself. The stress-test reveals that Lemma 4.4 is the linchpin of the 7/4 result, and its proof has a subtle gap: the transformation may alter the structure of the optimal offline schedule in a way that is not accounted for in the potential-function analysis. The paper argues that the transformation does not increase OPT's cost, but it does not argue that the optimal schedule for the transformed input is compatible with the analysis (which assumes a fixed optimal schedule independent of the random bits). The concrete test would settle whether this gap is real. If the test shows that the transformation can change the optimal schedule in a way that breaks the analysis, then the 7/4 result is not fully proven. If the test shows that the transformation always preserves the relevant structure, then the result stands. The verdict should be CONDITIONAL: accept subject to the authors providing a rigorous justification that Lemma 4.4 preserves the applicability of the potential-function analysis, or providing an alternative proof that does not rely on the transformation.","tokens_in":29471,"tokens_out":854,"duration_ms":10857,"concrete_test":"Construct a concrete 2-overlap input with self-overlap (e.g., two requests to the same element with overlapping windows, and a third request to a different element whose window overlaps both). Apply Lemma 4.4 to obtain a transformed input without self-overlap. Compute the optimal offline cost for both inputs. If the optimal cost for the transformed input is strictly less than for the original, then the inequality OPT(σ') ≤ OPT(σ) is strict, and the competitive ratio bound for the transformed input may not imply the same bound for the original. More importantly, check whether the optimal schedule for the transformed input can be mapped back to a feasible schedule for the original input with the same cost. If not, the analysis is incomplete.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's headline randomized result is that WBIT is 7/4-competitive on all 2-overlap inputs, removing the no-self-overlap assumption that is required for general k. This is achieved via Lemma 4.4, which transforms a 2-overlap input with self-overlap into one without self-overlap, preserving WBIT's cost and not increasing OPT's cost. The transformation works by shifting the release time of one of two overlapping requests to the same element to a later time c, chosen to be after the earlier deadline but before the later deadline, and such that no third request's window intersects the interval [b,c]. The load-bearing concern is that the transformation may change the set of feasible offline schedules in a way that the potential-function analysis of Section 4.1 (which assumes no self-overlap) no longer applies to the transformed input. Specifically, the transformation may create a situation where the offline schedule serves the two requests to the same element in a different order, or at different times, than in the original input, potentially invalidating the accounting of pre-service intervals and the µ and ν accounts. The paper argues that the transformation does not increase OPT's cost, but it does not prove that the optimal offline schedule for the transformed input is the same as the one used in the analysis. The analysis of WBIT in Section 4.1 relies on a fixed optimal schedule that is independent of the random bits. If the transformation changes the optimal schedule, the potential-function analysis may not hold. The paper does not provide a proof that the transformation preserves the structure of the optimal schedule in a way that is compatible with the analysis.","agreement_with_reader":"partial"},"referee_report":null,"author_rebuttal":null,"desk_editor":null,"pith_extraction":null,"created_at":"2026-11-13T10:12:23.569097+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":null,"supporting_citations":[],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}