Imagine twelve friends with diverse interests gathering for a trivia night, trying to split into two balanced teams. Zhang is well-versed in history and geography, Li knows pop music and movies inside out, and Wang excels in sports and cooking. To make both teams equally matched in every domain, team formation quickly hits a wall: as soon as you move Zhang to Team A to balance out the history score, Team A’s geography rating instantly shoots over the top, throwing the teams out of balance again in geography.
This seemingly ordinary team-building dilemma is known in mathematics as combinatorial discrepancy theory—the study of how to partition objects carrying multiple features into two groups while minimizing the differences between them. Whether balancing different car models and colors between two dealerships in used car sales, or dividing patients evenly into treatment and placebo groups in clinical trials, whenever multi-dimensional features are involved in partitioning, difficulty explodes as the number of features increases.
For decades, mathematicians have been searching for the theoretical boundaries of this group imbalance. In autumn 2025, computer scientists Nikhil Bansal and Haotian Jiang introduced a novel algorithm that dramatically slashed the upper bound of imbalance that had remained unbroken for nearly 30 years. Their research demonstrates that even when facing massive feature sets and vast populations, near-perfect balanced partitioning remains feasible.
Why Fair Partitioning Has Stumped Mathematicians for Decades
In everyday life, dividing objects with a single attribute is trivial. If you have 100 identical cakes, splitting them into two portions of 50 each achieves perfect balance. In reality, however, objects slated for distribution almost always carry multiple overlapping attributes simultaneously.
Take the used car dealership allocation scenario: vehicles sold at wholesale possess distinct body colors, vehicle models, and mileage figures. If split simply by total vehicle count, one dealership might end up with most of the convertibles while the other receives most of the red sedans. Both dealers want parity across every metric, but each attribute pulls the partitioning scheme in a different direction.
In medical trials, these pulling forces are even more tightly intertwined. Researchers partitioning participants into treatment and control groups must ensure similar age distributions while keeping blood pressure, underlying conditions, and lifestyle habits evenly matched. A severe imbalance along any single dimension could compromise the persuasiveness of trial data. These entangled feature attributes form a notoriously thorny tug-of-war board in the eyes of mathematicians.
A Math Conjecture Once Mocked as Reckless
To clarify the theoretical limits of partitioning, Hungarian mathematician János Komlós proposed the famous Komlós conjecture in the early 1980s. He conjectured that no matter how many objects are involved, and regardless of how many feature dimensions each object carries, one can always find a partition scheme such that the maximum numerical difference between the two groups across all features (known as discrepancy, which measures the gap in a specific attribute between two teams) does not exceed a fixed constant.
Komlós himself later joked that he only dared to propose the conjecture back then out of youthful rashness. Lacking effective mathematical tools at the time, proving a constant bound independent of the number of objects was immensely difficult, leading him to dub it an “irresponsible conjecture.”
The broader academic community engaged in a long relay over subsequent decades. In 1985, mathematician Joel Spencer proved that discrepancy could be bounded within the logarithm log N of the object count N; in 1998, Wojciech Banaszczyk further improved the upper bound to the square root of log N. From then on, the entire mathematical community stagnated before this record for nearly 30 years, with many scholars doubting whether the bound could ever be broken again.
An Algorithmic Breakthrough Born from a One-Week Visit
The turning point came in February 2025. Haotian Jiang, then a PhD student at the University of Washington and now at the University of Chicago, visited computer scientist Nikhil Bansal at the University of Michigan, Ann Arbor. Back in 2010, Bansal had designed an algorithm that split single objects and randomly perturbed their recombination, matching Spencer’s log N record.
On the second day of Jiang’s visit, the duo struck upon a fresh angle of breakthrough during their discussion. Following six months of rigorous derivation and refinement, they officially unveiled their new algorithm in autumn 2025, pushing the upper bound of maximum group discrepancy down to the fourth root of log N, or log(N)^(1/4). This marked the first theoretical breakthrough in the field in nearly three decades.
Figure: Mathematical concept diagram of vector tug-of-war and balanced partitioning. Source: Quanta Magazine / Ada Zejun Shen
Figure: The two researchers behind the Komlós conjecture breakthrough: Haotian Jiang (left) and Nikhil Bansal (right). Source: Quanta Magazine / Emily France, University of Michigan
How to Keep Tangled Attributes from Interfering
Previous partitioning algorithms typically focused only on the final cumulative global imbalance. As the number of attributes multiplied, adjustments applied to a single attribute often triggered a butterfly effect, violently disrupting the balance of other attributes.
Bansal and Jiang introduced a precise measurement of “dependency.” They designed a mechanism to evaluate how much random perturbations in one attribute would cause coupled, cascading changes in others.
By severing random inter-attribute interference during calculation, their algorithm successfully enabled each dimension to undergo independent, disturbance-free fine-tuning. This construction not only reduced the theoretical upper bound to the fourth root of log N, but also yielded an efficient algorithm that can be directly deployed and executed in real-world computing.
Partitioning Every Atom in the Universe Yields a Difference of Just 3
The fourth root of log N may sound abstract in mathematical formulas, but putting it into real-world scale reveals its striking impact.
When the number of objects N = 10, the fourth root of log N is roughly equal to 1. If you increase the object count to the estimated total number of atoms in the observable universe—about 10^81 (a 1 followed by 81 zeros)—the maximum discrepancy calculated by this formula only grows to around 3.
Yale mathematician Daniel Spielman remarked that within a human lifetime, one is unlikely ever to encounter a log fourth root value exceeding 5. This means that even if data scale expands to astronomical proportions, the degree of group imbalance remains virtually static, infinitely close to a constant.
University of Toronto researcher Aleksandar Nikolov confessed that he previously leaned toward believing the Komlós conjecture was false, but this new achievement re-convinced him that the conjecture is most likely true. Rainie Heck, a researcher at the Rényi Institute in Hungary, also noted that this theory is currently being integrated into the optimization of large language models and machine learning systems, and someone may soon fully prove the existence of a constant bound.
Near-Perfect Fairness Is Now Within Reach
Achieving absolute, zero-error fairness across infinitely complex features remains bounded by mathematical laws. Yet Bansal and Jiang’s breakthrough proves to the world that near-perfect balance is not only theoretically achievable, but also computationally efficient.
From a seemingly rash math conjecture 40 years ago to a 30-year fortress of square-root bounds, mathematicians have incrementally unlocked the theoretical limits of imbalance. Through an elegant algorithm, they have demonstrated that even when facing an intricately complex world, human intellect possesses the profound capacity to bring order out of chaos.
Reference link:
- Quanta Magazine Report
