A University of Chicago Computer Scientist Pushes Past a Long-Standing Math Barrier

For more than 40 years, mathematicians and computer scientists have wrestled with a deceptively simple question: If many overlapping requirements all need to be balanced at once, how evenly can it be done?

A new paper by Haotian Jiang of the University of Chicago’s Department of Computer Science and Nikhil Bansal from the University of Michigan marks one of the biggest advances in years on that problem. Their work resolves the Beck–Fiala conjecture in a broad regime, improves the best known bound for the more general Komlós problem, and introduces a new algorithmic technique that may reach beyond discrepancy theory.

The result is not a complete proof of the Beck–Fiala conjecture in every possible case. But it does break through a barrier that had held up the field for decades. In a very large and important range of cases, the authors show that the imbalance can be kept as small as mathematicians had long hoped. They also improve the best known results in many other settings. And for the broader Komlós problem (a more difficult version in which each object can influence many constraints at once) they make the first major improvement in decades.

“The Beck–Fiala conjecture is resolved for k≥(log⁡ n)^2, not in general,” Jiang said. “That’s almost the full regime (as the parameter k can range from 1 to the dimension) and lends strong support to the full conjecture, but currently we cannot prove the unconditional version.”

Discrepancy theory studies balance under conflicting demands. Jiang explains it through a clinical-trial analogy: imagine splitting thousands of patients into treatment and control groups while trying to keep age, blood pressure, smoking history, sex and prior conditions all balanced at once. Any one feature is easy enough to match. The difficulty is doing all of them simultaneously, since improving one category can worsen another.

That balancing problem has a distinctly computer-science flavor. It is about randomness, optimization and efficient procedures for navigating huge combinatorial spaces. Over time, discrepancy theory has become tightly connected to algorithm design, graph sparsification, approximation algorithms, numerical integration, kernel density estimation and randomized experiment design.

In the Beck–Fiala setting, each object affects at most k attributes. The conjecture from 1981 says the worst imbalance should scale like the square root of k, rather than growing in direct proportion to it.

The Komlós problem asks for something even stronger. Instead of assuming each object matters to only a few attributes, it allows every object to matter to all of them. The only restriction is that no single object can have too much total influence overall. In the clinical-trial picture, that means a patient could affect many different measures at once, but their combined importance is bounded. The conjecture says that even in this much more tangled setting, it should still be possible to divide the objects into two groups with only a constant worst-case imbalance.

Those claims have long seemed almost implausibly strong. Intuition suggests that balancing a few conditions should be easier than balancing millions. These conjectures suggest that, under the right structure, the sheer number of constraints should matter surprisingly little.

That is one reason the problem became so important. Another is that it serves as a gateway to many related questions, and the tools developed around it have spread widely through mathematics and theoretical computer science.

For decades, one obstacle kept resurfacing: researchers show that any single constraint was unlikely to become badly imbalanced, but controlling all constraints at once was much harder. The trouble was correlation. A method might keep one row under control without preventing many rows from going bad together.

Jiang and his collaborator attacked the problem with an algorithmic perspective. Modern discrepancy algorithms do not make all decisions at once. They begin with a fractional solution and then nudge it, step by step, toward a final assignment of plus or minus one. Each move is random, but carefully engineered.

Earlier methods ensured that each individual constraint saw something like a fair coin flip. That was enough to make one attribute behave well in isolation. It was not enough to prevent many attributes from going bad together.

The new work strengthens that control. Instead of requiring randomness only from the viewpoint of one constraint at a time, it requires whole collections of constraints to evolve in a more decoupled, random-like way. The authors call the idea affine spectral-independence. Technically, it is implemented through extra semidefinite programming constraints inside the algorithm. Conceptually, it gives the proof access to a stronger kind of probabilistic control.

“Our step has to satisfy that too, but we also demand something stronger: take a whole group of attributes, look at how the step changes all of their imbalances as a bundle, and require that this bundle look random-like as well,” Jiang said. “Roughly: not only should each attribute be unable to predict the step, the attributes should be unable to predict each other.”

That shift lets the authors prove something previous methods could not: not just that one bad imbalance is unlikely, but that many bad imbalances are unlikely to appear together. That is the key to beating the old union-bound barrier.

The result also underscores how closely modern discrepancy theory is tied to computation. This is not merely a proof that a good balancing exists in principle. The paper gives efficient polynomial-time algorithms for finding one. In fact, Jiang said, the constructive aspect was not secondary to the proof but central to it.

“The more interesting answer is that in this project the algorithm wasn’t a follow-up to the proof; it was the proof,” he said.

That algorithmic emphasis is part of what makes the work especially resonant in theoretical computer science. Semidefinite programming, random walks and correlation control are familiar tools in the area. Here they are assembled in a way that opens a new route through a problem many researchers had come to see as stuck.

The paper also changes the mood around the Komlós conjecture. For years, the best previous bound looked natural enough that some researchers suspected it might be the end of the story. By pushing below that threshold, Jiang and his collaborators have weakened one of the main reasons for doubting that Komlós might be true.

In practical terms, the improvement is larger than it first appears. A (\log n)^{1/4} factor grows extremely slowly. Even at immense scales, it stays small enough to make the conjectured constant bound feel far less remote than before.

The project grew out of earlier work by the authors that captured some of the right intuition in a more cumbersome form. That previous paper came close to the Beck–Fiala conjecture only in a narrower regime and gave no progress on Komlós. In revisiting it, they identified the underlying principle more cleanly: what they really needed was a way to enforce a kind of almost-independence across multiple constraints at once.

“There was, and interestingly, we had this moment on the second day Nikhil and I started this thread of discussion,” Jiang said, describing the point when the new perspective came into focus during a visit to the University of Michigan in early 2025.

The resulting framework has a layered structure. A basic version already beats the classical barrier. Stronger versions add further ingredients, including a multi-level strategy that hands problematic rows to more refined procedures and an adaptive variant that changes parameters over time. That modular design is one reason the method may prove useful beyond the specific conjectures tackled here.

Much remains open. The full Beck–Fiala conjecture is still unproved, and the full Komlós conjecture remains one of the major unsolved problems in discrepancy theory. Jiang says the current approach appears to hit a bottleneck around the log1/4 n scale for Komlós, suggesting that another new idea may be needed.

Still, after decades in which the field seemed trapped by an apparent probabilistic barrier, this work does something rarer than improve a bound. It changes the available toolkit. For mathematics and computer science alike, that is often how real progress begins.