Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-242 | 26th September 2026 00:30

On the Fixed-Order Strong Komlós Conjecture

RSS-Feed




TR26-242
Authors: Shiva Kintali
Publication: 9th October 2026 05:37
Downloads: 42
Keywords: 


Abstract:

The strong Koml\'os conjecture asserts that every ordered family of Euclidean-unit vectors admits a signing whose signed prefixes have uniformly bounded \(\ell_\infty\)-norm. We disprove this conjecture by constructing explicit finite families with unbounded fixed-order prefix discrepancy. At level \(k\), our integer matrix has \(d_k=2^{2^k-1}\) rows and exactly \(s_k=2^k\) nonzero \(\pm1\) entries per column. Every real coefficient assignment with magnitudes at least one produces a coordinate trajectory of range at least \(s_k\); after normalization, this yields prefix discrepancy at least \(\frac12\sqrt{s_k}=\frac12\sqrt{1+\log_2d_k}\to\infty\). Our construction uses a nested-word amplification with detector columns. It also gives linear lower bounds for sparse binary matrices, square \(N\times N\) examples with discrepancy \(\Omega(\sqrt{\log\log N})\), and separations from ordinary discrepancy and freely reordered prefix discrepancy.



ISSN 1433-8092 | Imprint