Tighter bounds on Komlós discrepancy: existence and algorithmic results
Abstract
Guo, Fang, and Lu recently proved the Komlós conjecture: for vectors v1,…,vn∈ℝd of Euclidean norm at most one, there are signs εj∈{−1,1} with |∑jεjvj|∞≤3√(2π). We give a short proof of the bound 3π that keeps the geometric lifting framework of (Guo, Fang, and Lu 2026a) while replacing the analytic core by a quadratic Dirichlet energy. Moreover, using a more fine-grained analysis of the stability of the product-cosine function of (Smirnov and Vershynin 2026) under translations, we further sharpen the bound to below $6.9013$. On the algorithmic side, based on the polynomial-time construction of (Guo, Fang, and Lu 2026b) we give a deterministic algorithm that finds a coloring of discrepancy at most $37.54$ using at most Õ(mn+n4) arithmetic operations.
Related
- Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
- Tighter Regret Bounds for Contextual Action-Set Reinforcement Learning
- Improved Explicit and Algorithmic Lower Bounds for r(5,t)
- Tight bounds for positive discrepancy via eigenvalues
- Existence and multiplicity results for third-order ordinary differential equations with derivative dependence subject to the Riemann–Stieltjes integral boundary conditions
BibTeX
@misc{akbas2026tighter,
title = {{Tighter bounds on Komlós discrepancy: existence and algorithmic results}},
author = {Emrullah Akbas and Suvrit Sra},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.27172},
eprint = {2609.27172},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.27172},
}
RIS
TY - UNPB
TI - Tighter bounds on Komlós discrepancy: existence and algorithmic results
AU - Emrullah Akbas
AU - Suvrit Sra
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.27172
UR - https://arxiv.org/abs/2609.27172
AB - Guo, Fang, and Lu recently proved the Komlós conjecture: for vectors v_1,…,v_n∈ℝ^d of Euclidean norm at most one, there are signs ε_j∈{−1,1} with |∑_jε_jv_j|_∞≤3√(2π). We give a short proof of the bound 3π that keeps the geometric lifting framework of (Guo, Fang, and Lu 2026a) while replacing the analytic core by a quadratic Dirichlet energy. Moreover, using a more fine-grained analysis of the stability of the product-cosine function of (Smirnov and Vershynin 2026) under translations, we further sharpen the bound to below $6.9013$. On the algorithmic side, based on the polynomial-time construction of (Guo, Fang, and Lu 2026b) we give a deterministic algorithm that finds a coloring of discrepancy at most $37.54$ using at most Õ(mn+n^4) arithmetic operations.
ER -