First Major Progress on the Komlós Conjecture in Nearly 30 Years: Bansal + Jiang's 'Split-in-Half' Algorithm Pushes High-Dimensional Discrepancy to Nearly Constant

In fall 2025, Nikhil Bansal (theoretical computer scientist, University of Michigan) and Haotian Jiang (theoretical computer scientist, University of Chicago) jointly announced the first major advance in nearly 30 years on the Komlós conjecture, a 'holy grail' problem in combinatorial discrepancy theory. They established an upper bound whose growth with dimension is astonishingly slow—even at astronomically large dimensions, the bound sits within a hair of a universal constant. Other researchers described the work as "very exciting," "a beautiful result," and "huge progress." The result does not fully settle the Komlós conjecture (which requires the discrepancy bound to be a fixed constant independent of dimension), but it provides the strongest evidence yet that Komlós's seemingly 'irresponsible' conjecture may actually be true.

To appreciate the weight of this result, one must go back to the 1980s.

The 'Irresponsible' Conjecture

János Komlós proposed a counterintuitive conjecture in the early 1980s:

> No matter how many objects you consider (say, 12 quiz enthusiasts) or how many dimensions (categories like Greek mythology, college basketball, geography, music), the discrepancy—which is quantifiable—never exceeds a constant.

In plain terms: given any N vectors (each with its own strengths and weaknesses across categories), there exists a way to split them into two teams such that the imbalance in every dimension is controlled within a fixed constant—independent of N and independent of the number of dimensions.

If true, the conjecture defies intuition: usually more dimensions means harder to balance, yet Komlós claimed a 'universal constant' as a safety net. Komlós himself joked in an email: "I was young and foolish when I proposed it. With this irresponsible conjecture, I dropped a bomb on combinatorial discrepancy theory."

Only Two Advances in 30 Years

Over the past 30 years, the Komlós conjecture saw only two significant advances:

• 1985: Joel Spencer (NYU) improved the discrepancy bound to O(log N) (logarithmic growth).
• 1998: Wojciech Banaszczyk pushed the bound to O(√log N) (square-root-of-log growth).

Both advances depended on the dimension parameter: in higher dimensions the bound still grows slowly, far from the 'universal constant' Komlós wanted. The field at one point believed the problem could not be pushed further—many researchers thought an exact solution simply did not exist.

The Key Idea: Splitting in Half

In 2010, Bansal came up with a seemingly counterintuitive method: cut each vector in half.

> "I can split a person in half," Bansal said in a Quanta Magazine report.

The traditional approach assigns each vector wholly to one team (multiplying all coordinates by +1 or -1). Bansal's scheme 'cuts' each vector in half—half to team A, half to team B—then uses a randomized process to gradually 'repair' the split, letting each vector's final assignment slowly converge to one team.

The key is that throughout this 'split + repair' process, the discrepancy never explodes. Bansal and Jiang proved that even at astronomical dimensions, the final discrepancy bound grows extremely slowly—only a hair away from a constant.

Haotian Jiang of the University of Chicago was the other key figure; his doctoral thesis and subsequent work, polished together with Bansal, produced the final scheme. Aleksandar Nikolov (University of Toronto) commented: "I used to lean toward believing the conjecture was false; this work now makes me more confident the conjecture may be true."

Why 'A Hair Away' Matters

The mathematical community generally believes that going from 'almost constant' to 'strictly constant' requires fundamentally new ideas. Between the 1998 O(√log N) bound and 'constant' there was a qualitative gap; the 2025 result compresses that gap to a quantitative one. This means:

• Almost all algorithms and applications relying on discrepancy theory can swap the old bound for the new one.
• Within the next 6–12 months, a second breakthrough converting the 'hair' into a 'strict constant' is quite plausible.
• The Komlós conjecture has shifted from 'looks false' to 'looks very likely true.'

The method itself has independent value: reducing a complex high-dimensional problem into tractable pieces via 'split-in-half + repair' resonates naturally with divide-and-conquer and combination ideas in machine learning algorithms.

Cross-Disciplinary Implications

Combinatorial discrepancy theory spans operations research, computer science, machine learning, statistics, and more:

• Operations research: fair allocation, scheduling optimization, capacity assignment (e.g., fairly splitting passengers between two shuttles).
• Machine learning: low-rank matrix factorization, sampling algorithms, stability of stochastic gradient methods.
• Statistics: experimental design, covariate balance in A/B testing.
• Theoretical computer science: communication complexity, approximation algorithms, derandomization of randomized algorithms.

If the Komlós conjecture is ultimately proved, all of these fields gain tighter bounds and better algorithmic guarantees. Even the 2025 'nearly constant' result already suffices to force rewritten convergence-rate proofs in several subfields.

One-Sentence Summary: For the First Time in 30 Years, Someone Has 'Seen' Komlós's Boundary

The previous major advance in discrepancy theory was Banaszczyk's O(√log N) work in 1998. Twenty-seven years later, Bansal and Jiang used a 'split-in-half + repair' algorithmic idea to push the bound to the edge of 'almost constant.' This is not the end, but a beginning—it tells everyone who doubted Komlós from outside: the person you doubted may be closer to the truth than you imagined.

Data Points

• Early 1980s: János Komlós proposes the conjecture (discrepancy bound = universal constant, independent of dimension)
• 1985: Joel Spencer pushes the bound to O(log N)
• 1998: Wojciech Banaszczyk pushes the bound to O(√log N)
• 2010: Bansal proposes the 'split-in-half + repair' algorithmic idea
• Fall 2025: Bansal (University of Michigan) + Jiang (University of Chicago) announce the first major progress in nearly 30 years
• New bound: changes with dimension extremely slowly—within a hair of a constant even at astronomical dimensions
• Aleksandar Nikolov (University of Toronto): previously leaned toward the conjecture being false, now leans toward true
• Komlós himself joked he was "young and foolish" when proposing it
• Application areas: operations research, computer science, machine learning, statistics, combinatorics
• Peer reactions: "very exciting," "a beautiful result," "huge progress"
• Publication venue expected at the level of Annals of Mathematics or Inventiones Mathematicae (official announcement pending)
• Watch for: whether a second breakthrough achieves 'from almost constant to strictly constant' within 12 months