OpenAlex ·
Tighter bounds on Komlós discrepancy: existence and algorithmic results
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2609.27172
- Original
- Read it at the publisher
- Topics
Abstract
Guo, Fang, and Lu recently proved the Komlós conjecture: for vectors $v_1,\ldots,v_n\in\mathbb R^d$ of Euclidean norm at most one, there are signs $\varepsilon_j\in\{-1,1\}$ with $\|\sum_j\varepsilon_jv_j\|_\infty\le3\sqrt{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 $\widetilde O(mn+n^4)$ arithmetic operations.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Minimal representations of topology-preserving quantum-like states
Boolean threshold functions, neuron capacity, and memory retrieval
Sampling Line-Graph Colorings with Constant Extra Colors
Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7
A 27 x 27 x 27 counterexample to Comon's conjecture
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.