Major Progress on Komlós's Conjecture: Bansal and Jiang Push Discrepancy Bounds to Nearly Constant

In fall 2025, Nikhil Bansal (University of Michigan) and Haotian Jiang (University of Chicago) announced the first major breakthrough in nearly 30 years on Komlós's conjecture, often described as the "holy grail" of combinatorial discrepancy theory. They proved an upper bound on discrepancy whose dependence on dimension is remarkably slow — even for astronomically large dimensions, the bound stays within a hair's breadth of a universal constant. Fellow researchers have called the work "very exciting," "a beautiful result," and "a huge advance." The conjecture itself remains open, but this result is the strongest evidence yet that Komlós's counterintuitive claim may be true.

The "Irresponsible" Conjecture

In the early 1980s, János Komlós proposed a conjecture that sounded too good to be true: no matter how many vectors you have, or how many dimensions, there is always a way to split them into two groups so that the imbalance in every dimension is bounded by a fixed constant. Komlós himself later joked in an email: "I was young and foolish when I made it. With this irresponsible conjecture, I dropped a bomb on discrepancy theory."

30 Years, Only Two Advances

• 1985: Joel Spencer (NYU) improved the bound to O(log N).
• 1998: Wojciech Banaszczyk pushed it to O(√log N).

Both bounds still grew with dimension, far from the conjectured universal constant, and many researchers believed the problem could not be pushed further.

The Split-in-Half Idea

In 2010, Bansal proposed a counterintuitive method: split each vector in half. Instead of assigning each vector wholly to one side (multiplying all coordinates by +1 or −1), the approach assigns half of each vector to each team, then uses a randomized process to gradually "repair" the split until every vector converges to one side. The key contribution of the new Bansal–Jiang work is proving that discrepancy never blows up during this split-and-repair process — the final bound differs from a constant by only a negligible amount, regardless of dimension.

Aleksandar Nikolov (University of Toronto) commented: "I used to lean toward the conjecture being false. This work makes me more confident it might be true."

Why "Almost Constant" Matters

Moving from "nearly constant" to "exactly constant" typically requires fundamentally new ideas. The 1998 O(√log N) bound and a constant were separated by a qualitative gap; the 2025 result compresses it to a quantitative one. Researchers expect:

• Algorithms relying on discrepancy theory can immediately adopt the tighter bound.
• A follow-up breakthrough achieving a strict constant within 6–12 months is plausible.
• The conjecture has shifted from "seems implausible" to "seems likely true."

Cross-Disciplinary Impact

Combinatorial discrepancy theory underpins work in:

• Operations research: fair allocation, scheduling, capacity assignment.
• Machine learning: low-rank matrix factorization, sampling, stability of stochastic gradient methods.
• Statistics: experimental design, covariate balancing in A/B testing.
• Theoretical computer science: communication complexity, approximation algorithms, derandomization.

A full proof of Komlós's conjecture would yield tighter guarantees across all these fields; even the current near-constant bound already lets several subfields rewrite their convergence-rate proofs.

Timeline

• Early 1980s: Komlós proposes the conjecture (universal constant bound, dimension-independent).
• 1985: Spencer achieves O(log N).
• 1998: Banaszczyk achieves O(√log N).
• 2010: Bansal introduces the "split and repair" algorithmic idea.
• Fall 2025: Bansal and Jiang announce a near-constant bound — the first major progress in ~30 years.

Source reporting: Quanta Magazine.