Computer Scientists Achieve First Major Advance on Komlós Conjecture in 30 Years

Theoretical computer scientists Nikhil Bansal of the University of Michigan and Haotian Jiang of the University of Chicago have made the first significant progress on the Komlós conjecture since 1998. The conjecture, proposed by mathematician János Komlós in the early 1980s, predicts that when allocating objects with multiple attributes between two groups, the imbalance — or discrepancy — can always be kept below a universal constant, regardless of the number of objects or attributes.

Previous bounds on discrepancy grew with the problem's size. In 1985, Joel Spencer capped discrepancy at the logarithm of the number of vectors N, and Wojciech Banaszczyk improved this to the square root of log N in 1998. Bansal and Jiang's new algorithm achieves a bound of the fourth root of log N, a value that remains remarkably small even for astronomically large N. For N equal to the estimated number of atoms in the observable universe (10^81), the bound is only 3.

The researchers built on Bansal's earlier algorithmic approach, which splits vectors into halves and uses a random process to gradually assign them to groups while controlling discrepancy. Their key innovation was designing the algorithm to reduce 'dependency' — the extent to which a random perturbation in one attribute affects the discrepancy in others. By carefully managing these joint impacts, they gained greater control over how discrepancy evolves at each step.

The result has surprised experts who previously doubted the conjecture. Aleksandar Nikolov of the University of Toronto said the advance makes him 'quite a bit more confident that probably the conjecture actually is true.' Daniel Spielman of Yale University noted that the fourth root of log N is 'getting pretty close to constant for every practical purpose.'

Beyond its theoretical significance, the algorithm is computationally efficient, according to Rainie Heck of the Alfréd Rényi Institute of Mathematics. This efficiency means it could be applied to other open problems in discrepancy theory, optimization, physics, finance, and machine learning. Heck studies how discrepancy theory can improve large language models and other machine learning systems.

While the Komlós conjecture remains unproven, the new bound represents the strongest evidence yet that a universal constant may exist. The work demonstrates how algorithmic methods can tackle problems that purely mathematical approaches struggled with for decades, offering a new pathway toward resolving one of discrepancy theory's 'holy-grail problems.'