Browse
Log in / Register
Share
Imagine you’re splitting a dozen trivia buffs into two teams, each with strengths in geography, music, movies, and sports. The goal is perfect balance in every category. Sounds impossible? Mathematicians call it a discrepancy problem, and for decades one of the field’s most famous unsolved puzzles—the Komlós conjecture—has promised that such balance is always within reach, bounded by a universal constant. In March 2025, a new algorithmic breakthrough brought that tantalizing promise closer to reality than ever before.
The Komlós conjecture, proposed by Hungarian mathematician János Komlós in the early 1980s, states that no matter how many objects (or dimensions) you try to split, you can always keep the imbalance below a fixed constant. For trivial matters like dividing 12 people into two teams, the claim seems almost too good to be true. “This is really astonishing,” says Haotian Jiang, a theoretical computer scientist at the University of Chicago. “The Komlós conjecture says it has nothing to do with the dimension of the problem. It’s a universal constant.”
Despite decades of effort, the best upper bound before 2025 grew with the number of dimensions—a far cry from constant. In 1998, Wojciech Banaszczyk proved a bound of √log N, where N is the number of vectors. Then, in fall 2025, Nikhil Bansal of the University of Michigan and Haotian Jiang announced a new limit that changes so slowly with dimension that even with an astronomical number of dimensions, it is only a hair away from constant. “It’s a huge step forward,” says Aleksandar Nikolov, a computer scientist at the University of Toronto. “I used to lean toward thinking the conjecture is false, but this work is now making me quite a bit more confident that probably the conjecture actually is true.”
The key to their advance was a novel algorithmic approach. Bansal and Jiang built on techniques Bansal pioneered in 2010, where he “split” each vector in half and then gradually massaged the halves to the correct team while keeping discrepancy in check. The 2016 version matched Banaszczyk’s bound. Now, by adding extra restrictions that constrain how discrepancy accumulates across dimensions, they pushed the bound even lower. “I can throw half-baked ideas at him, and he picks it up,” Bansal says of his collaboration with Jiang. “And he can do the same.”
The new work has already sparked excitement among researchers. “This gives a new method on a problem that people had kind of no approaches for,” says Raghu Meka, a computer scientist at UCLA. The result also has implications beyond pure mathematics: discrepancy theory underpins resource allocation, clinical trial design, and even machine learning. If the Komlós conjecture is fully proven, it could unlock answers to many other problems in operations research and theoretical computer science.
Even Komlós himself, now retired, is amused by the decades-long hunt. “I was young and foolish when I made it,” he joked in an email. “I threw a wrench into combinatorial discrepancy theory with this irresponsible conjecture.” But with Bansal and Jiang’s latest result, that wrench may finally be turning into a solution.
The full proof of the conjecture remains elusive, but the gap has never been smaller. “We are now within a rounding error of the constant,” Bansal says. “It’s the most compelling evidence yet that Komlós was right all along.” As the research community digests the new algorithm, many expect further refinements in the coming months—and perhaps a final resolution to one of discrepancy theory’s holy grails.
