Computer scientists have achieved the first major improvement in nearly 30 years on a fundamental mathematical problem concerning how objects can be divided as evenly as possible between two groups.
The breakthrough, by theoretical computer scientists Nikhil Bansal and Haotian Jiang, advances the study of the Komlós conjecture, one of the central unresolved questions in combinatorial discrepancy theory.
Their new algorithm dramatically improves the best-known mathematical guarantee for balancing high-dimensional collections of objects. Although it does not completely prove the Komlós conjecture, researchers say the result provides some of the strongest evidence yet that the decades-old prediction may ultimately be correct.
The Mathematics of Imbalance
The work belongs to discrepancy theory, a branch of mathematics concerned with dividing objects or resources into groups while keeping differences between the groups as small as possible.
A simple example is dividing people into two trivia teams. Each person might have different strengths in history, mathematics, sports, literature or science. The goal is not simply to give both teams the same number of players, but to distribute those different abilities as evenly as possible.
Similar mathematical problems arise when dividing resources, assigning participants to experimental groups, distributing inventory and balancing complex datasets.
The challenge becomes much harder when each object possesses many different attributes simultaneously.
The Komlós Conjecture
In the early 1980s, mathematician János Komlós proposed a remarkable prediction about such balancing problems.
In mathematical terms, objects can be represented as vectors, with each coordinate describing one of their attributes. The challenge is to split these vectors between two groups so that the imbalance — known as the discrepancy — remains as small as possible.
Komlós conjectured that no matter how many vectors or dimensions are involved, there should always be a way to divide them so that the discrepancy remains below a universal constant.
If true, this would mean that even extremely complicated, high-dimensional systems could always be balanced surprisingly well.
The conjecture has resisted proof for more than four decades and has been described as one of the major unresolved problems in discrepancy theory.
Why the Problem Has Been So Difficult
Mathematicians have long known ways to place upper limits on discrepancy, but those limits have continued to increase as the size or dimensionality of the problem grows.
In 1985, mathematician Joel Spencer established an important bound involving the logarithm of the number of vectors.
A further major advance came in 1998 when Wojciech Banaszczyk improved the bound to approximately the square root of the logarithm of the number of vectors.
That remained the strongest known general result for decades.
But it was still fundamentally different from what Komlós predicted: a fixed constant that would not grow with the size of the problem.
Computer Scientists Enter the Problem
Beginning in the late 2000s, theoretical computer scientists started developing algorithmic approaches to discrepancy theory.
Bansal was among the researchers who pioneered this shift.
In 2010, he introduced an algorithmic method in which vectors were initially divided fractionally between two groups and then gradually assigned completely to one side or the other through a controlled randomized procedure.
The algorithm was designed to prevent discrepancy from becoming too large during the assignment process.
This showed that solutions previously known to exist mathematically could also be approached through explicit algorithms.
In 2016, Bansal refined his method sufficiently to match Banaszczyk's long-standing discrepancy bound.
The next goal was more ambitious: use algorithmic methods not merely to reproduce existing mathematical results, but to surpass them.
Bansal and Jiang Find a New Approach
Bansal later began collaborating with Haotian Jiang, now a theoretical computer scientist at the University of Chicago.
Their work focused on one particularly difficult feature of discrepancy problems: different dimensions are deeply interconnected.
Improving balance in one attribute can unintentionally worsen it in another.
For example, two groups of cars could contain equal numbers of each colour while still having a major imbalance in the number of convertibles. Correcting the convertible imbalance could then disturb the previously balanced colour distribution.
This interdependence makes high-dimensional balancing exceptionally difficult.
Bansal and Jiang searched for a way to uncover a form of hidden independence within these apparently interconnected effects.
Measuring Dependency
Their breakthrough involved controlling not only the overall discrepancy but also what they described as dependency.
The algorithm examines how changing one attribute affects discrepancies in other attributes.
As in Bansal's earlier methods, vectors are first fractionally distributed between the two groups. The algorithm then gradually turns those fractional assignments into complete assignments.
The key difference is that the new procedure carefully controls how random changes in one dimension influence the others.
By limiting these joint effects, Bansal and Jiang achieved substantially tighter control over how discrepancy accumulates during the process.
A New Record After Nearly 30 Years
The result is a major improvement in the mathematical upper bound.
For N vectors, the new algorithm guarantees discrepancy of at most approximately the fourth root of log(N).
The previous long-standing bound depended on the square root of log(N).
Although both quantities technically increase as N grows, the fourth root increases extraordinarily slowly.
The improvement therefore brings the mathematical guarantee much closer to the constant bound predicted by Komlós.
It represents the first major advance on the general Komlós problem in nearly three decades.
Almost Constant in Practice
The striking feature of the new result is how slowly the new bound grows.
Even for extraordinarily large values of N, the fourth root of its logarithm remains small.
This makes the new result behave almost like a constant for many conceivable problem sizes, although mathematically it is still not the universal constant required to prove the Komlós conjecture.
Researchers interviewed by Quanta Magazine described the development as a major and unexpected improvement.
Some scientists who had previously suspected that the Komlós conjecture might be false now say the new result has increased their confidence that it could ultimately be proved.
Potential Impact Beyond Pure Mathematics
The importance of discrepancy theory extends beyond the original balancing problem.
The field has connections with optimization, theoretical computer science, physics, operations research, finance and machine learning.
Because Bansal and Jiang's method is algorithmically efficient, researchers may be able to adapt its ideas to other mathematical and computational problems.
The underlying principle — finding ways to limit interactions between many interconnected variables — could be especially valuable in complex optimization systems.
Researchers are also investigating how discrepancy methods could contribute to machine-learning problems, including work involving large language models.
The Komlós Conjecture Is Still Open
Despite the significance of the breakthrough, Bansal and Jiang have not proved the full Komlós conjecture.
Their bound still grows, however slowly, with the number of vectors. Komlós' conjecture requires a universal constant that remains unchanged regardless of the dimensionality or size of the system.
The researchers themselves believe that moving beyond the new fourth-root logarithmic bound will probably require a fundamentally different mathematical idea.
Nevertheless, the result has renewed optimism around a problem that had seen little progress for decades.
It demonstrates that extremely complicated high-dimensional systems can be balanced far more closely than previous mathematics could guarantee — and brings researchers another important step toward understanding whether Komlós' remarkable constant bound truly exists.
Research reference
Nikhil Bansal and Haotian Jiang. Research advancing the Komlós discrepancy problem and improving the general upper bound to approximately log(N)¹⁄⁴. Preprint: arXiv:2508.03961