{"id":"1528b9a5-5bb0-4802-8305-169e0975cbe3","arxiv_id":"2607.14238","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new online random-walk algorithm achieves O(√d) prefix discrepancy for d-sparse vectors whenever d ≥ log(T)(log log T)^{2+η}, proving Beck–Fiala in that regime and resolving the online Spencer conjecture.","lead":"This paper gives a fast online algorithm that keeps prefix discrepancy at the optimal O(√d) for sparse binary matrices with sparsity down to barely logarithmic in the number of columns. It settles an open online balancing conjecture and extends the offline Beck–Fiala bound to a much wider regime.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central claim hinges on unproved Lemma 2.6 (three-way coupling); if the lemma is mis-stated or false, the online algorithm cannot output genuine signs and Theorem 1.1 collapses.","rationale":"We read the paper in good faith. The main theorem is a strong extension of online Beck–Fiala, and the proof is a coherent multi-scale construction: a bump-law stationary measure (Section 3), a scale-sensitive curvature envelope (Lemma 3.2), weighted concentration via majorization (Lemma 2.9), and a three-walk coupled algorithm (Proposition 2.7). I checked the stationarity computation, the convexity/balance criterion, the boundary estimates, and the tail bounds; they are internally consistent. The only step that is not self-contained is Lemma 2.6, the finite three-way coupling. This is the exact point the Reader identified as weakest. The paper's claim that the algorithm is efficient and correct depends on this lemma existing for all marginals in the stated range and being constructible. Since the lemma is cited rather than proved or formally verified, and since a counterexample would invalidate Theorem 1.1, this is the load-bearing concern. A finite LP / Fourier–Motzkin check would settle it. No other internal flaw was found; the m/n typo in Proposition 3.5 is a presentation issue only and does not affect the application where support size ≤d. The reader's CONDITIONAL verdict remains the right recommendation: conditional on the validity of Lemma 2.6, the central claim is supported.","tokens_in":8737,"tokens_out":36259,"duration_ms":327722,"concrete_test":"Verify Lemma 2.6 by computing the projection of the polytope of distributions on the 12 outcomes (six triples summing to +1, six summing to −1) onto the marginal parameters (a_j,b_j). Use Fourier–Motzkin elimination or linear programming over a dense grid to confirm that the achievable set is exactly {0≤a_j,b_j≤1/3, a_j+b_j≥1/3}. Also inspect the cited proof in [1] to ensure the statement matches this exact parameter range and is efficiently constructible.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing assumption is Lemma 2.6, cited from [1]. The entire sign-generation mechanism in Proposition 2.7 reduces to this coupling: at every step, three balanced Metropolis samples (with marginals p±) are coupled so that δ1+δ2+δ3 ∈ {−1,1}; the algorithm then outputs ε_t = that sum. If Lemma 2.6 is false as stated, or if it requires additional constraints not present in Definition 2.3 and the bounds p±≤1/3, a_j+b_j≥1/3, then no valid ε_t is produced and the prefix-discrepancy identity Σ ε_t v_t = Σ_j (X_k,j − X_0,j) fails. The paper gives no proof or verification of Lemma 2.6, only a citation from a 2026 preprint. The lemma is the unique external, non-black-box step: the stationarity lemma, curvature envelope, and weighted concentration tails are derived in detail and appear internally consistent. I found no internal error in §3, but the correctness of the central theorem is conditional on this unverified finite coupling lemma.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims a randomized online algorithm for the online Beck--Fiala problem: for every fixed η>0, whenever d ≥ C log T (log log T)^{2+η}, the prefix discrepancy of any d-sparse sequence in [-1,1]^n is O(√d) with high probability. The method couples three Metropolis-type walks with a compactly supported invariant product density, uses a three-way coupling lemma to convert their increments into genuine signs, and proves scale-sensitive curvature tails via a majorization reduction. The authors state as consequences the offline Beck--Fiala conjecture at sparsity d ≥ log^{1+o(1)} T and online prefix Spencer for T ≤ exp(c n / log^{2+η}(en)). The proof is terse but the main chain — stationarity, curvature criterion, majorization, and tail estimates — is internally coherent; the principal open point is the unproved finite coupling lemma (Lemma 2.6), which is load-bearing for the correctness of the sign-generation mechanism.","tokens_in":8996,"tokens_out":33077,"duration_ms":289942,"significance":"If the result is correct, it is a major advance: it gives the first online algorithm with optimal O(√d) prefix discrepancy for Beck--Fiala sparsity down to a nearly logarithmic range, and it answers a conjecture of Kulkarni, Reis, and Rothvoss in the online Spencer setting. The stationary-measure construction and the tail machinery are interesting in their own right, and the proof is largely self-contained apart from the cited coupling lemma. The constants are explicit and the algorithm is conceptually simple, which are strengths. However, because the correctness of the central theorem is conditional on Lemma 2.6, which is stated without proof and only attributed to an arXiv preprint, the paper cannot be accepted in its present form.","major_comments":[{"comment":"The entire sign-generation mechanism of Proposition 2.7 is delegated to this finite coupling lemma, but the manuscript provides no proof of it and no theorem number or page pointer in [1]. Since Theorem 1.1 collapses if the coupling does not exist or is not efficiently constructible, this is a load-bearing missing verification. The authors should include a complete proof of Lemma 2.6, or state precisely where in [1] it is proved, and should confirm that the hypotheses cover every triple of marginal probabilities arising from Definition 2.3, including the boundary cases p±v = 1/3.","section":"§2.2, Lemma 2.6"},{"comment":"The statement defines X = (LY_1, ..., LY_m) in R^m while the hypothesis is phrased with v ∈ R^n, and the proof indexes v_i for i ≤ m. The application in Theorem 1.1 needs the uniform balance estimate (8) over all v with ||v||_2 ≤ 1 and ||v||_∞ ≤ d^{-1/2}. The constants in (27) are independent of v, so the reduction to the support of v is valid, but it should be stated formally: take m = |supp v| and regard v as an element of R^m, then use Proposition 2.7 with V equal to the whole allowed family.","section":"§3.3, Proposition 3.5"}],"minor_comments":[{"comment":"The sentence 'the prefix discrepancy ... is at most C'√d' should say 'with high probability' (or give a concrete probability bound), since the algorithm is randomized and the preceding display is only a tail bound.","section":"Theorem 1.1, consequence paragraph"},{"comment":"The definition of ℓ(x) appears to be log^q(e x) rather than 'log q(ex)'; the missing superscript makes the display confusing.","section":"§3, Eq. (14)"},{"comment":"References [4] and [5] both list the same arXiv identifier (arXiv:2508.03961); the Bansal--Jiang entry should be checked and corrected.","section":"References"},{"comment":"The stationarity proof is very terse. Expanding the line in which the two min-terms cancel with the p0 term would improve readability.","section":"§2.1, Lemma 2.2"},{"comment":"The paper calls the algorithm 'efficient' but does not state a running time. If the coupling in Lemma 2.6 is constructive, the complexity should be stated explicitly; if it is not, the efficiency claim should be softened.","section":"§2.3, Proposition 2.7"}],"recommendation":"major_revision","confidential_remarks":"The mathematical core appears promising, and I did not find an internal inconsistency in §3. The key unresolved item is the unproved coupling lemma, Lemma 2.6. The authors should be asked to either prove it or give a precise, accessible reference; without that, the paper is conditional. As an editor, you may also wish to verify that the AI-usage disclosure is consistent with the journal's policy and that reference [1] is publicly available and correctly cited."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing you should know: this paper claims the online Beck–Fiala bound O(√d) for d down to log^{1+o(1)} T, which would also resolve the online Spencer conjecture. The proof is a genuine advance, but it inherits a heavy load from a single external lemma—Lemma 2.6, the three-way coupling from Aden-Ali [1]—that the authors do not prove. If that lemma is right, the paper works; if it is misstated or doesn't hold online, Theorem 1.1 collapses.\n\nWhat's actually new: the compactly supported bump invariant measure and the scale-sensitive curvature envelope are original, and they fit together with the stationarity argument and the majorization reduction to yield the result. The proof chain from Lemma 2.2 through Proposition 3.5 appears internally coherent. The result extends the offline Beck–Fiala range from d ≥ log² T down to d ≥ (log T)(log log T)^{2+η}, and Corollary 1.3 answers Conjecture 1 of Kulkarni–Reis–Rothvoss in the online Spencer setting. That is a real contribution, not an incremental one.\n\nThe main soft spot is, again, Lemma 2.6. It is stated cleanly, but a referee needs to see a proof or a precise pointer to a verified version in Aden-Ali's preprint. The paper also shows signs of haste: two references share the same arXiv identifier, the notation log_q is never defined, and many constants are absorbed without comment. The AI-use disclosure is unusual; the authors say they manually checked, but independent verification is still missing. None of these are fatal by themselves.\n\nThis is a paper for discrepancy theorists and for anyone working on online vector balancing. It deserves a serious referee. The right response is to send it to review, with a request that the authors either prove Lemma 2.6 in an appendix or give a detailed derivation from Aden-Ali's work. I would not desk-reject this.","headline":"A strong, plausible online Beck–Fiala breakthrough that should go to review, but the whole argument leans on an unproved coupling lemma from another preprint.","tokens_in":9548,"tokens_out":2319,"would_cite":true,"duration_ms":24962,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","11K38","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"A randomized online algorithm keeps prefix discrepancy at O(sqrt d) for d-sparse vectors once d reaches C log T (log log T)^(2+η), extending the offline Beck–Fiala conjecture to near-logarithmic sparsity.","keywords":["online discrepancy","Beck–Fiala conjecture","prefix discrepancy","sparse vectors","random walk","stationary measure","vector balancing","Spencer setting"],"falsifier":"Check the coupling lemma by exhaustive search: enumerate all triples (a_j,b_j) on a fine grid (say multiples of 0.01) satisfying 0 ≤ a_j,b_j ≤ 1/3 and a_j+b_j ≥ 1/3, and solve the linear feasibility problem for a joint distribution on {−1,0,1}^3 with prescribed marginals and support restricted to configurations whose coordinate sum is ±1. A single triple with no feasible coupling disproves the lemma and removes the main mechanism of the proof. Alternatively, run the proposed algorithm on random d-sparse sequences with d just above C log T (log log T)^(2+η) and look for prefix discrepancies exc","tokens_in":8611,"feed_emoji":"⚖️","tokens_out":5786,"duration_ms":53697,"temperature":0.7,"pith_summary":"The paper tries to establish that the Beck–Fiala bound O(sqrt d) can be achieved not just offline but by an online algorithm, and that it holds for sparsity d as small as roughly log T times a polylogarithmic factor. If true, this resolves the offline Beck–Fiala conjecture in that regime and answers the open question of online vector balancing in the Spencer setting. The central claim is a probability bound: with high probability, the maximum prefix discrepancy stays below a constant times sqrt d whenever each incoming vector has at most d nonzero entries and d is at least C log T (log log T)^(2+η). The construction is a random walk with a compactly supported invariant measure, run in triplicate, whose three increments are coupled to sum to a genuine sign. The interest is that it crosses a threshold where no online algorithm can do better: for d = o(log T), prefix discrepancy must grow faster than sqrt d.","feed_headline":"Online balancing hits O(sqrt d) discrepancy once d nears log T","feed_subtitle":"A randomized walk with three coupled copies keeps prefix error optimal for sparsity down to (log T)^(1+o(1)), resolving an open conjecture.","key_machinery":"The central object is the invariant measure: a product of identical one-dimensional densities ρ with compact support and very flat, high-curvature 'walls' near the boundary (the bump law h_β(y) proportional to exp(-exp((1-y^2)^(-β)))). The walk at each step proposes moving by ±v or staying, with Metropolis probabilities using the ratio of the invariant density; this keeps the state distribution exactly stationary. Three such walks are run in parallel, and a finite three-way coupling lemma is used to correlate their ±/0 increments so the three increments sum to either +1 or -1, which becomes the algorithm's sign. The key quantitative tool is the curvature criterion: a state is 'balanced' for","core_discovery":"On its own terms, the discovery is that a carefully chosen one-dimensional 'bump' density — essentially exp(-exp((1-y^2)^(-β))) on (-1,1), scaled to (-L,L) — gives a stationary, compactly supported product law for a Metropolis-type random walk, and that three copies of this walk can be coupled so that their steps add to a genuine ±1 sign at every round. The balance condition needed for the coupling is expressed through the second derivative (curvature) of the potential U = -log ρ, and the paper shows that for d-sparse vectors the relevant weighted curvature has a nearly exponential tail. This yields the theorem: for every fixed η > 0, with constants depending only on η, the online prefix dis","pith_inferences":["The same three-walk coupling may transfer to other discrepancy settings where a stationary compact measure can be constructed, for example to sharpen constants in Komlós-type bounds.","Because the balance condition only uses coordinate-wise second differences, the method may extend to weighted or non-binary entries as long as the vector has bounded l2 norm and l∞ norm; the normalization here already allows entries in [-1,1].","The proof's explicit reliance on an oblivious adversary suggests that the algorithm fails against an adaptive adversary; a natural question is whether any adaptive-adversary algorithm can achieve similar prefix bounds in this sparsity regime.","The appearance of (log log T)^(2+η) hints at a possible limit: the method likely cannot reach d = C log T without removing the polylogarithmic factor, and the existing lower bound already prevents going below log T."],"forward_implications":["For every fixed η > 0, whenever d ≥ C log T (log log T)^(2+η), the offline Beck–Fiala conjecture holds: every d-sparse binary matrix has discrepancy O(sqrt d).","The online Spencer setting is resolved: for T = n (and somewhat longer horizons), there is a randomized online algorithm guaranteeing prefix discrepancy O(sqrt n) for arbitrary vectors in [-1,1]^n.","The threshold in d is essentially optimal for online algorithms: no algorithm can keep prefix discrepancy O(sqrt d) when d = o(log T), even against an oblivious adversary.","The failure probability is small enough to survive a union bound over T steps, so the guarantee holds simultaneously for every prefix with probability close to 1."],"fun_headline_variants":["Online Beck-Fiala bound met at log-scale sparsity","Online algorithm solves Beck-Fiala for near-log sparsity","Optimal online discrepancy for sparsity near log T","Random walk achieves online Beck-Fiala at log sparsity","Online prefix discrepancy optimal down to log^(1+o(1)) sparsity"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The argument stands on the finite coupling lemma that for any three pairs (a_j,b_j) with each probability between 0 and 1/3 and a_j+b_j ≥ 1/3, one can jointly sample three {−1,0,1} variables with those marginals whose sum is always ±1; if that lemma is false or cannot be implemented online, the algorithm's signs are not guaranteed and the prefix discrepancy bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Online Beck-Fiala bound met at log-scale sparsity","Online algorithm solves Beck-Fiala for near-log sparsity","Optimal online discrepancy for sparsity near log T","Random walk achieves online Beck-Fiala at log sparsity","Online prefix discrepancy optimal down to log^(1+o(1)) sparsity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001607,"raw_usage":{"total_tokens":6256,"prompt_tokens":785,"completion_tokens":5471,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":529,"completion_tokens_details":{"reasoning_tokens":5386}},"tokens_in":529,"tokens_out":5471,"duration_ms":37219,"temperature":1.0,"reasoning_tokens":5386,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T02:42:05.411492+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check the coupling lemma by exhaustive search: enumerate all triples (a_j,b_j) on a fine grid (say multiples of 0.01) satisfying 0 ≤ a_j,b_j ≤ 1/3 and a_j+b_j ≥ 1/3, and solve the linear feasibility problem for a joint distribution on {−1,0,1}^3 with prescribed marginals and support restricted to configurations whose coordinate sum is ±1. A single triple with no feasible coupling disproves the lemma and removes the main mechanism of the proof. Alternatively, run the proposed algorithm on random d-sparse sequences with d just above C log T (log log T)^(2+η) and look for prefix discrepancies exc","supporting_citations":[],"review_version":1}