Imbalance may really be bounded: a near-proof of the Komlos conjecture

In fall 2025, Nikhil Bansal of the University of Michigan and Haotian Jiang of the University of Chicago announced the first major advance in nearly 30 years on the Komlos conjecture, reporting an upper limit on discrepancy that changes so slowly with the number of dimensions that it is only a hair away from constant even at astronomical dimension ^[9]. That matters because the previous best limit, from 1998, still depended strongly on the dimension and was far from constant ^[8], which is to say it weakened exactly as the problem got wider.

Discrepancy theory is the study of allocating resources as evenly as possible ^[1]. The standard setup breaks a collection into two subsets: trivia teams, used cars into lots, or clinical trial participants into treatment and placebo groups ^[15]. The Komlos version treats each object as a unit vector whose coordinates measure how much of each attribute it carries; assign it to one team and its coordinates stay put, assign it to the other and every coordinate is multiplied by -1 ^[14]. The leftover imbalance is the discrepancy. In the early 1980s Janos Komlos conjectured that this imbalance never has to exceed a fixed amount, no matter how many objects or how many attributes you track ^[2]. "The Komlos conjecture says it has nothing to do with the dimension of the problem. It's a universal constant," Jiang told Quanta Magazine ^[3].

The shape of that statement is what makes it useful. A bound that does not grow with dimension is a bound you can still quote when the attribute count is large; a bound that grows is a promise that quietly expires. No one has ever found a counterexample, and yet the claim is strong enough that some mathematicians thought it had to be false ^[5]. Komlos, now retired, told Quanta by email that he was "young and foolish" when he made it and that he "threw a wrench into combinatorial discrepancy theory with this irresponsible conjecture" ^[6]. Bansal calls proving it "one of these holy-grail problems in discrepancy theory" ^[4].

The new work does not resolve the problem ^[11]. Its immediate value is evidential, and the market in beliefs is moving: Aleksandar Nikolov of the University of Toronto, who says he "used to lean toward thinking the conjecture is false," told Quanta the result is "now making me quite a bit more confident that probably the conjecture actually is true" ^[12]. That is a shift on a question that has been open for roughly 45 years ^[17], with 27 years between the 1998 bound and this one ^[16].

Two details are worth holding on to. First, according to Quanta's account, a true Komlos conjecture would unlock answers to other problems inside discrepancy theory and in fields such as operations research ^[7], and the authors' insights are said to carry potential applications in mathematics, physics and machine learning ^[13]. Those are claims about future work, not delivered results. Second, the method was described as a novel algorithmic approach ^[9]. For anyone who has to produce a balanced split rather than argue that one exists, that distinction is the whole point.

What to watch: whether the residual dependence on dimension can be removed outright, closing the conjecture ^[11]; whether the algorithmic technique transfers to the adjacent problems the conjecture is supposed to unlock ^[7]; and whether the researchers who leaned toward "false" follow Nikolov ^[12].