For the first time in three decades, computer scientists have found a better way to distribute objects evenly between two groups. The advance, which tackles a long-standing puzzle known as the Komlós problem, marks a significant step in discrepancy theory—a field that studies how to minimize imbalance when perfect fairness is impossible.
The Komlós problem, first posed by mathematician János Komlós in the 1980s, asks whether there is a universal constant that bounds the maximum imbalance when assigning vectors to two groups. The best previous bound, established in the early 1990s, was proportional to the square root of the logarithm of the number of vectors. Now, a new result by computer scientists Nikhil Bansal and Haotian Jiang has reduced that bound to the fourth root of the logarithm, a dramatic improvement that has surprised many in the field.
“I used to think that the bound that was known before was just the right bound, and we just had to find a way to prove that we cannot do any better,” said Aleksandar Nikolov, a computer scientist at the University of Toronto. “So I was definitely surprised that we could do a lot better.”
The new bound is not just a theoretical curiosity. As Daniel Spielman of Yale University notes, “The fourth root of log(N) is very small. Like in your life, you will not see a number for which the fourth root of log(N) is more than 5. … It’s getting pretty close to constant for every practical purpose.” This means that for all practical applications, the imbalance is nearly as small as the conjectured constant bound.
The breakthrough reaffirms a central insight of discrepancy theory: even when perfect balance is out of reach, achieving near-perfect balance is not only possible but often practical. The new algorithm is efficient, according to Rainie Heck of the Alfréd Rényi Institute of Mathematics in Hungary, which could allow researchers to apply it to other open problems in discrepancy theory and beyond—including questions in optimization, physics, and finance. Heck herself studies how discrepancy theory can improve large language models and other machine learning systems.
The result has also reinvigorated the hunt for Komlós’ “irresponsible” constant bound, a conjecture that a fixed constant (independent of the number of vectors) suffices. Nikolov and Spielman both expressed newfound confidence in the conjecture. “It’s very rare that that’s the right answer to any problem,” Spielman said, referring to the fourth-root bound, which suggests that the true limit might be even lower.
Bansal, however, cautions that the algorithmic approach he has used since 2010 may not be enough to reach the constant bound. “We hit a wall at a quarter root,” he said. “Going beyond that will definitely require something very new.” Still, the progress has given researchers hope. “I do think,” Heck said, “that someone will be able to prove it.”
The new work is a reminder that even in mathematics, where problems can remain open for decades, unexpected advances can come from fresh perspectives. As the field continues to explore the boundaries of discrepancy theory, this result may open doors to new techniques and applications, from AI reasoning to river network modeling. The quest for the ultimate bound continues, but for now, the fourth root is a milestone worth celebrating.
