Online Beck--Fiala Down to Logarithmic Sparsity
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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.14238
curl -X POST /api/v1/records/arxiv/2607.14238/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.14238/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'