← 研踪 PaperTrailarXiv:2607.14238 · v2
Online Beck--Fiala Down to Logarithmic Sparsity
首次提交 2026-07-16 02:01
版本更新 2026-11-03 11:05
雷达观测 2026-11-04 23:40
摘要
The celebrated (offline) 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)$. In this note, we consider the {\it online} version of the conjecture. For every fixed $η>0$, we give a randomized online algorithm that achieves $O_η(\sqrt d)$ prefix discrepancy for every fixed sequence of $d$-sparse vectors $a_t\in[-1,1]^n$, except with probability at most \[ C_ηT\exp\left[-\frac{c_ηd}{\log^{2+η}(ed)}\right]. \] In particular, this gives an optimal $O(\sqrt d)$ discrepancy upper bound for $d\geq C_η(\log T)(\log\log T)^{2+η}$. This range of sparsity is optimal up to $\log\log T$ factors. The result also resolves in strong form the {\it online Spencer problem}, corresponding to the case $d = n$. The algorithm is based on a compactly supported Metropolis walk, constructed by combining ideas from several recent works on online vector balancing. 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.
作者备注：Minor revision - simplified proof and significantly expanded the exposition
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 11:05 · 最新观测版本
Online Beck--Fiala Down to Logarithmic Sparsity
The celebrated (offline) 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)$. In this note, we consider the {\it online} version of the conjecture. For every fixed $η>0$, we give a randomized online algorithm that achieves $O_η(\sqrt d)$ prefix discrepancy for every fixed sequence of $d$-sparse vectors $a_t\in[-1,1]^n$, except with probability at most \[ C_ηT\exp\left[-\frac{c_ηd}{\log^{2+η}(ed)}\right]. \] In particular, this gives an optimal $O(\sqrt d)$ discrepancy upper bound for $d\geq C_η(\log T)(\log\log T)^{2+η}$. This range of sparsity is optimal up to $\log\log T$ factors. The result also resolves in strong form the {\it online Spencer problem}, corresponding to the case $d = n$. The algorithm is based on a compactly supported Metropolis walk, constructed by combining ideas from several recent works on online vector balancing. 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.
查看此版本解读 →查看此版本原文 ↗