Pith. sign in

REVIEW 2 major objections 5 minor 2 cited by

Online Beck--Fiala Down to Logarithmic Sparsity

T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2607.14238 v1 pith:NWNNSFSM submitted 2026-07-15 math.CO cs.DMcs.DSmath.PR

Dylan J. Altschuler , Konstantin Tikhomirov This is my paper · ORCID
classification math.COcs.DMcs.DSmath.PR MSC 05D4011K3868W27
keywords onlinediscrepancyBeck–FialaconjectureprefixsparsevectorsrandomwalkstationarymeasurevectorbalancingSpencersetting
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [§2.2, Lemma 2.6] 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.
  2. [§3.3, Proposition 3.5] 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.
minor comments (5)
  1. [Theorem 1.1, consequence paragraph] 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.
  2. [§3, Eq. (14)] The definition of ℓ(x) appears to be log^q(e x) rather than 'log q(ex)'; the missing superscript makes the display confusing.
  3. [References] References [4] and [5] both list the same arXiv identifier (arXiv:2508.03961); the Bansal--Jiang entry should be checked and corrected.
  4. [§2.1, Lemma 2.2] The stationarity proof is very terse. Expanding the line in which the two min-terms cancel with the p0 term would improve readability.
  5. [§2.3, Proposition 2.7] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation is a composition of independent external lemmas and self-contained probabilistic estimates.

full rationale

The paper's derivation chain is linear and non-circular. Proposition 2.7 reduces the discrepancy bound to a high-probability balance condition, which is then verified in Proposition 3.5 using explicit, self-contained density choices (the bump law) and concentration inequalities (Lemmas 3.1–3.3, Proposition 3.4). The parameters β and L are chosen to satisfy proof inequalities, not fitted to any target discrepancy value. The only external load-bearing input is Lemma 2.6 (the three-way coupling), cited from Aden-Ali [1]; this is a finite probabilistic statement independent of the theorem's conclusion, and the paper does not claim to derive it from its own results. No self-citations appear, no ansatz is smuggled via citation, and no known result is renamed. The chief concern—that Lemma 2.6 is unproved in the present manuscript—is a correctness or verification gap, not circularity, since the lemma does not assume the theorem's bound and the theorem does not reduce to it by construction.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on two external black boxes: Aden-Ali's three-way coupling lemma (used to generate genuine signs from three coupled walks) and the KRR lower bound (used for optimality). The paper introduces a new invariant density parameterized by β and a support radius L; these are proof constants, not fitted to data. No new physical entities are introduced.

free parameters (2)
  • β
    Shape parameter of the invariant bump density; chosen as β ≥ 2/η purely to make the exponent q = 2+2/β in the tail bound ≤ 2+η. No data dependence.
  • L
    Support radius chosen large enough that L² ≥ K′_β/(2 log 2), where K′_β is a universal constant from Proposition 3.4. This choice ensures the curvature-balance condition D_v ≤ 2 log 2 holds with high probability. Not fitted to any data.
assumptions (4)
  • domain assumption Three-way coupling lemma (Lemma 2.6) from Aden-Ali [1] is valid and constructible: given three pairs (aj,bj) with 0≤aj,bj≤1/3 and aj+bj≥1/3, there exists a coupling with δ1+δ2+δ3 ∈ {−1,1}.
    Proposition 2.7's online sign generation relies entirely on this external finite coupling result; the present paper does not prove it or give an explicit algorithm to find the coupling.
  • domain assumption The input vectors are fixed by an oblivious adversary (Remark 2.8).
    The stationarity and union-bound argument requires v_t to be independent of the algorithm's private state; the paper explicitly notes the proof does not extend to adaptive adversaries.
  • domain assumption KRR lower bound (Remark 1.4) asserting Ω(√log T) online prefix discrepancy for d = o(log T).
    Used to claim essential optimality of the sparsity range in Theorem 1.1; cited from [8] and not proved here.
  • standard math Standard probability tools (Chernoff, conditional Jensen, Cauchy–Schwarz, majorization) are valid.
    Used throughout Lemmas 2.9, 3.2, 3.3, and 3.4; these are standard and accepted.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Beck--Fiala Down to Logarithmic Sparsity." pith.science (2026). https://pith.science/paper/NWNNSFSM

@misc{pith2026260714238,
  author       = {Pith},
  title        = {Pith review of: Online Beck--Fiala Down to Logarithmic Sparsity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NWNNSFSM}},
  note         = {Machine review of arXiv:2607.14238}
}
abstract

The Beck--Fiala conjecture asserts that every matrix $A\in\{0,1\}^{n\times T}$ with at most $d$ nonzero entries in each column has discrepancy $O(\sqrt d)$. A major breakthrough result of Bansal and Jiang recently established the validity of the conjecture for $d \ge \log(T)^2$. The present article extends the validity of the classical \textit{offline} Beck--Fiala conjecture to $d \ge \log(T)^{1+o(1)}$; moreover, the main thrust of the result is that it is actually obtained by an efficient \textit{online} algorithm that minimizes prefix discrepancy. The result is also essentially optimal, since online prefix discrepancy is known to scale as $\omega(\sqrt{d})$ for $d =o(\log T)$. As an immediate corollary, the open question of online vector balancing in the Spencer setting is also resolved. The algorithm is based on a compactly supported Metropolis fixed-point walk, constructed by combining ideas from several recent works on the online Koml\'os problem. The proof was generated in conversation with ChatGPT 5.6 Pro; the authors provided high-level guidance in several rounds of prompting, followed by manual checking and rewriting of the proof.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Online Discrepancy Minimization for Sub-Gaussian Inputs via Regularization and Restriction

    cs.DS 2026-08 conditional novelty 7.0 of 10

    An online potential-based algorithm achieves O(sqrt n) terminal discrepancy with exponentially high probability for independent sub-Gaussian inputs, and a sparsity-aware variant achieves O(sqrt k).

  2. Online balancing of vectors with small coordinates

    math.CO 2026-08 accept novelty 6.0 of 10

    This paper achieves constant prefix discrepancy for online signed balancing of small-coordinate vectors with failure probability about T exp(-c d / ln^2(ed)), and proves the ln^2 scale is a barrier for the compact-pot...

Reference graph

Works this paper leans on

9 extracted references · 5 linked inside Pith · cited by 2 Pith papers

  1. [1]

    Aden-Ali,Optimal online discrepancy minimization in linear time, arXiv:2607.04388, 2026

    I. Aden-Ali,Optimal online discrepancy minimization in linear time, arXiv:2607.04388, 2026

    arXiv 2026

  2. [2]

    Alweiss, Y

    R. Alweiss, Y. P. Liu, and M. Sawhney,Discrepancy minimization via a self-balancing walk, inProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 14–20, 2021

    2021

  3. [3]

    Banaszczyk,Balancing vectors and Gaussian measures ofn-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360

    W. Banaszczyk,Balancing vectors and Gaussian measures ofn-dimensional convex bodies, Random Structures & Algorithms 12 (1998), 351–360

    1998

  4. [5]

    Bansal and H

    N. Bansal and H. Jiang,Decoupling via affine spectral-independence: Beck–Fiala and Koml´ os bounds beyond Banaszczyk, inProceedings of the 58th Annual ACM Symposium on Theory of Computing, 432–442, 2026; arXiv:2508.03961

    arXiv 2026

  5. [6]

    Bansal and J

    N. Bansal and J. Spencer,On-line balancing of random inputs, inRandom Structures & Algorithms, 2020; arXiv:1903.06898

    arXiv 2020

  6. [7]

    Integer-making

    J. Beck and T. Fiala,“Integer-making” theorems, Discrete Applied Mathematics 3 (1981), 1–8

    1981

  7. [8]

    Kulkarni, V

    J. Kulkarni, V. Reis, and T. Rothvoss,Optimal online discrepancy minimization, inProceedings of the 56th Annual ACM Symposium on Theory of Computing, 1832–1840, 2024; arXiv:2308.01406

    arXiv 2024

  8. [9]

    Y. P. Liu, A. Sah, and M. Sawhney,A Gaussian fixed point random walk, in13th Innovations in Theoretical Computer Science Conference, LIPIcs 215, 101:1–101:10, 2022

    2022

Show all 9 references
  1. [10]

    Smirnov and R

    G. Smirnov and R. Vershynin,Discrepancy and Fisher information, arXiv:2605.13107, 2026. Department of Mathematics, The University of Texas at Austin Email address:dylan.altschuler@austin.utexas.edu Department of Mathematical Sciences, Carnegie Mellon University Email address:k...

    2026 arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.