{"id":"d3e99e2f-3caa-4658-ab62-43d782e424cb","arxiv_id":"2607.04388","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Coupling three Gaussian fixed-point walks yields an O(dT)-time online algorithm with optimal O(√log T) prefix discrepancy for unit vectors.","lead":"A linear-time online algorithm assigns random signs to arriving vectors so every partial sum equals the sum of three standard Gaussians, achieving the optimal O(√log T) discrepancy bound. This closes the exponential-time gap for the best known online Komlós guarantee and yields a fast algorithmic version of Banaszczyk’s bound.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates Proposition 5 as the enabling condition for the coupling, and that condition holds by a short case analysis on the inner product ⟨x,v⟩ versus ∥v∥_{2}^{2}/2. The remainder of the argument (invariance, induction, sub-Gaussian tail via Hölder, union bound) is standard once the three marginal Gaussians are available. Because the paper is short, parameter-free, and the key algebraic steps are elementary, ordinary human verification risk is low and does not rise to a load-bearing concern. The AI-discovery disclosure does not affect soundness. Consequently the ACCEPT verdict stands without adjustment.","tokens_in":10383,"tokens_out":554,"duration_ms":7005,"concrete_test":"Independently re-derive the density identity in the proof of Proposition 4 (the rewriting of p^{+}_v(x) via the Gaussian density ratio and the subsequent cancellation that yields f(x)=γ(x)) without consulting the paper; if the identity fails for any x or any ∥v∥_{2}≤1 the invariance collapses. As a secondary numerical check, sample 10^{4} independent Gaussians in d=2, apply one step of the three-way coupling for a fixed unit vector v, and verify that the empirical covariance of each updated coordinate remains within 0.05 of the identity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on the Gaussian fixed-point walk (Prop. 4) remaining invariant under the balanced transition probabilities of Prop. 5, which in turn enable the three-way coupling of Lemma 6 that forces ε_t=δ_{t,1}+δ_{t,2}+δ_{t,3}∈{±1} while preserving the three marginals. Both the density-ratio calculation establishing invariance and the elementary bounds p^{+},p^{-}≤1/3 together with p^{+}+p^{-}≥1/3 (when ∥v∥_{2}≤1) are short, self-contained, and appear free of hidden assumptions or circularity. The subsequent induction that each G_{t,j} stays standard Gaussian and that S_t equals their sum is deterministic once the coupling exists. No load-bearing gap is visible in the argument that would invalidate Theorems 1–2.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper gives a linear-time online algorithm (the Gaussian triplet walk) for the online Komlós problem. For any fixed sequence of vectors with Euclidean norm at most 1, the algorithm assigns each arriving vector a random sign so that every prefix sum equals the sum of three coupled standard Gaussians. Consequently the prefix discrepancy is O(√log T) with high probability, matching the optimal bound of Kulkarni–Reis–Rothvoss while improving their exponential runtime to O(dT). The same construction yields a linear-time algorithmic version of Banaszczyk’s bound for the offline Komlós problem. The argument rests on a carefully balanced Gaussian fixed-point walk (Propositions 4–5), a three-way coupling that forces the sum of three fractional signs to be ±1 while preserving the prescribed marginals (Lemma 6 / Algorithm 1), and a short induction that keeps each auxiliary walk marginally standard Gaussian.","tokens_in":10648,"tokens_out":711,"duration_ms":5911,"significance":"The result closes a clear complexity gap: the optimal online prefix-discrepancy bound was previously known only via an exponential-time construction, while the best linear-time algorithms achieved only O(log T). The new algorithm is elementary, fully self-contained, and runs in optimal linear time. The same technique immediately supplies a linear-time algorithmic realization of Banaszczyk’s theorem, improving on a long line of polynomial-time algorithms. The explicit three-way coupling and the balance condition under the unit-norm assumption are clean contributions that may be reusable for other online discrepancy or online vector-balancing problems. The manuscript also records that the algorithm and main proof were discovered with the aid of a large language model; the mathematical content itself is independent of that provenance and stands on its own.","major_comments":[],"minor_comments":[{"comment":"In the proof of Theorem 2 the inequality exp(−x/a) ≤ a exp(−x) is invoked for a = ∥P_t e_k∥₂² ≤ 1 and x ≥ 1. While correct, a one-line justification (or a reference to the elementary inequality t e^{1−t} ≤ 1 for t ∈ (0,1]) would make the step fully transparent.","section":null},{"comment":"Algorithm 1 asserts that a feasible point x can be found greedily, but the concrete implementation of the greedy step is only sketched. Adding a short pseudocode fragment or an explicit loop would remove any residual ambiguity for implementers.","section":null},{"comment":"The constant 18 appearing in the final discrepancy bound can be tightened slightly by a more careful application of Hölder (or by using the exact sub-Gaussian parameter of the sum of three independent Gaussians). The improvement is cosmetic but worth a remark.","section":null},{"comment":"A few typographical inconsistencies remain (e.g., “Koml´ os” vs. “Komlós”, occasional missing spaces around math operators). A final pass would polish the presentation.","section":null}],"recommendation":"accept","confidential_remarks":"The AI-discovery statement is unusual but does not affect correctness or novelty of the mathematics. The paper is a clean, high-quality contribution that fits a top theory venue; I see no reason to delay acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper gives the first O(dT) online algorithm that matches the optimal O(√log T) prefix discrepancy of Kulkarni–Reis–Rothvoss. The device is simple: run three carefully balanced Gaussian fixed-point walks, couple their fractional updates so their sum is always a genuine sign, and keep each walk marginally standard Gaussian. Prefix sums are therefore 3-subgaussian and the concentration is immediate.\n\nWhat is new is the coupling itself (Lemma 6 + Algorithm 1). Earlier Gaussian walks either stayed fractional or needed large variance to force integer signs with high probability; here the unit-norm balance condition (Prop. 5) guarantees that the three transition probabilities never put too much mass on any single choice, so a short, explicit three-way coupling can force ε_t ∈ {±1} while preserving the exact marginals. The invariance proof (Prop. 4) is a one-line density-ratio calculation, the induction is deterministic once the coupling exists, and the whole argument is self-contained. Runtime is literally linear: three inner products and a constant-time sample per step.\n\nSoft spots are minor. The concrete constant 18 in the final bound is a bit loose (Hölder + a crude projection/union bound), and the greedy construction of the coupling point x is only sketched, but both are easy to tighten or implement. No free parameters, no circular definitions, and the AI-use disclosure is transparent. The offline corollary recovers Banaszczyk in linear time, which is already useful even if Bansal–Jiang later improved the offline exponent.\n\nThis is for people who care about algorithmic discrepancy, online balancing, or constructive versions of Banaszczyk-type results. The proofs are short enough that a careful referee can verify them in an afternoon. I would send it to peer review without hesitation; it is a clean, correct closing of a known gap.","headline":"Linear-time optimal online Komlós via a clean three-Gaussian coupling; the math checks out and closes the exponential-time gap.","tokens_in":11177,"tokens_out":495,"would_cite":true,"duration_ms":5550,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W20","68Q25","60G50"],"pacs":[],"model":"grok-4.5","headline":"An online algorithm assigns signs so every prefix sum is three standard Gaussians, giving optimal discrepancy in linear time.","keywords":["online discrepancy","Komlós problem","Gaussian fixed-point walk","prefix discrepancy","subgaussian concentration","linear-time algorithm","vector balancing"],"falsifier":"Run the algorithm on a sequence of unit vectors for which the optimal online discrepancy is known to be Ω(√ log T) and check whether the observed max-norm of the prefix sums exceeds the stated O(√ log T) high-probability bound, or verify that after any step the three auxiliary states fail to be standard Gaussian.","tokens_in":11303,"feed_emoji":"⚖️","tokens_out":921,"duration_ms":9025,"temperature":0.7,"pith_summary":"The paper gives a fast online method for signing unit vectors so that no partial sum gets large in the infinity norm. When vectors arrive one by one and each must be signed immediately, the algorithm keeps three carefully coupled Gaussian walks whose updates always add to a genuine ±1 sign. Because the prefix sum equals the sum of three standard Gaussians, ordinary concentration yields the optimal O(√ log T) bound with high probability, matching the best previous (but exponentially slow) result. The same procedure also supplies a linear-time algorithmic version of Banaszczyk’s classical offline bound. A sympathetic reader cares because optimal online discrepancy is now practical rather than merely existential.","feed_headline":"Online signs keep every prefix sum three Gaussians","feed_subtitle":"Optimal O(√ log T) discrepancy now runs in linear time instead of exponential time","key_machinery":"The Gaussian triplet walk: three copies of a balanced Gaussian fixed-point walk are coupled by a three-way sampler so that the sum of their fractional updates is always a genuine ±1 while each coordinate remains marginally N(0,I).","core_discovery":"For any sequence of vectors with Euclidean norm at most 1, the Gaussian triplet walk produces random signs ε_t such that every prefix sum equals G_{t,1} + G_{t,2} + G_{t,3} where each G_{t,j} is marginally a standard Gaussian; the algorithm runs in O(dT) time and therefore achieves max_t ||∑_{i=1}^t ε_i v_i||_∞ = O(√ log T) with high probability.","pith_inferences":["The same balanced fixed-point walk may admit couplings with more than three copies, potentially improving the constant in front of √ log T.","Because the method is purely online and linear-time, it can be dropped into streaming or distributed discrepancy settings where exponential-time algorithms cannot run.","If the balance condition can be restored for vectors longer than 1 by rescaling or rejection, the algorithm would extend beyond the Komlós regime."],"forward_implications":["The optimal O(√ log T) online Komlós bound is now achievable in linear time rather than exponential time.","Banaszczyk’s O(√ log min{d,T}) offline bound admits a simple O(dT)-time randomized algorithm.","Any norm whose unit ball has Gaussian measure concentration inherits the same online guarantee by the same sub-Gaussian argument.","The construction supplies an explicit coupling that keeps three invariant Gaussians while forcing signed updates."],"fun_headline_variants":["Linear-time signs make every prefix sum three Gaussians","Online discrepancy hits O(√log T) via three-Gaussian walk","O(dT) algorithm couples prefixes to three standard Gaussians","Optimal online discrepancy now runs in linear time","Gaussian triplet walk achieves optimal prefix discrepancy online"],"cache_read_input_tokens":128,"weakest_assumption_plain":"When every vector has Euclidean length at most 1, none of the three transition probabilities of the fixed-point walk ever exceeds one-third and their sum is always at least one-third, which is exactly what lets the three-way coupling force a real sign.","fun_headline_variants_meta":{"raw":{"variants":["Linear-time signs make every prefix sum three Gaussians","Online discrepancy hits O(√log T) via three-Gaussian walk","O(dT) algorithm couples prefixes to three standard Gaussians","Optimal online discrepancy now runs in linear time","Gaussian triplet walk achieves optimal prefix discrepancy online"]},"model":"grok-4.5","effort":"low","cost_usd":0.00336,"raw_usage":{"total_tokens":1138,"prompt_tokens":771,"num_sources_used":0,"completion_tokens":84,"cost_in_usd_ticks":33600000,"prompt_tokens_details":{"text_tokens":771,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":283,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":771,"tokens_out":84,"duration_ms":3491,"temperature":1.0,"reasoning_tokens":283,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T19:31:27.371065+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Run the algorithm on a sequence of unit vectors for which the optimal online discrepancy is known to be Ω(√ log T) and check whether the observed max-norm of the prefix sums exceeds the stated O(√ log T) high-probability bound, or verify that after any step the three auxiliary states fail to be standard Gaussian.","supporting_citations":[],"review_version":1}