Constructive Discrepancy Minimization

17 concepts13 papers1 proposal

Imagine you are handed a collection of items and a list of overlapping groups containing those items. Your goal is to split the items into two balanced teams—let's call them $+1$ and $-1$—such that within every single group, the number of players from each team is as close to equal as possible. The maximum imbalance across all groups is what we call the discrepancy of the system.

For decades, discrepancy theory was a field of stunning mathematical guarantees paired with profound computational frustration. Mathematicians could prove that remarkably balanced colorings must exist, but their proofs offered no way to actually find them. Recently, a powerful shift in theoretical computer science has bridged this "existential-constructive gap," turning abstract geometric existence proofs into efficient, polynomial-time algorithms.

The Existential Wall

The classical era of discrepancy theory relied heavily on non-constructive methods like the probabilistic method, the pigeonhole principle, and high-dimensional volume arguments. For instance, Joel Spencer’s landmark 1985 proof showed that any set system with $n$ elements and $n$ sets has a coloring with a discrepancy of at most $6\sqrt{n}$.

The catch? The proof used an entropy-based counting argument. It demonstrated that the number of "good" colorings was strictly greater than zero, meaning at least one had to exist. However, because these good colorings are buried within an exponentially large search space, searching for them blindly is computationally intractable. As noted by Luh et al., this disconnect between sharp theoretical bounds and practical algorithms has long been the primary obstacle to deploying discrepancy theory in real-world applications.

Why the Gap Matters

This algorithmic gap is not just an academic inconvenience; it limits practical problem-solving across several domains:

  • Experimental Design and Sampling: In machine learning, deterministic sampling techniques like "herding" are used to approximate data distributions. Harvey et al. showed that while discrepancy theory guarantees the existence of optimal vector sequences for sampling, the lack of constructive algorithms historically prevented these bounds from being applied to real-world datasets.
  • Scheduling Theory: Minimizing the total time jobs spend waiting in a system (flow time) can be modeled as a prefix discrepancy problem. Bansal et al. demonstrated that while convex geometry guarantees low-error scheduling configurations, non-constructive proofs leave practical, real-time scheduling algorithms out of reach.
  • Combinatorial Geometry and Operations: From the classic work of Daniel J. Kleitman on piercing convex sets to modern retail assortment optimization studied by Will Ma, knowing that an optimal configuration or subset exists does not help a system compute the actual coordinates or item lists needed in production.

The Breakthrough: Walking on the Edges

The key to unlocking these non-constructive proofs came from a shift in perspective: instead of trying to guess a discrete $\pm 1$ coloring immediately, algorithms should start in a continuous space and gracefully converge to a discrete solution.

The foundational mechanism for this is the "Edge-Walk" algorithm introduced by Lovett et al.. To understand why it works, imagine the space of all possible fractional colorings as a high-dimensional hypercube $[-1, 1]^n$. A fully discrete coloring corresponds to one of the corners of this hypercube.

   Continuous Origin              Orthogonal Steps             Discrete Corner
 [ 0.0,  0.0,  0.0 ]  --->  [ 0.4, -0.2,  1.0 ]  --->  [ 1.0, -1.0,  1.0 ]
                                          ^
                                    Variable Fixed!
  1. Start at the Origin: The algorithm begins at the center of the hypercube, $x = (0, 0, \dots, 0)$, where every element is colored fractionally.
  2. Define Active Constraints: As the algorithm takes small random steps, the discrepancy of some sets will start to approach their allowed theoretical threshold. These sets are flagged as "active constraints."
  3. Move in the Null Space: To ensure the discrepancy of these active sets does not get any worse, the algorithm restricts its next step to the kernel (or null space) of the active constraint matrix. Because the step vector is orthogonal to the rows representing the active sets, moving along this vector changes the fractional colors of the elements but keeps the discrepancy of the critical sets perfectly constant.
  4. Lock Variables: Eventually, an element's fractional color will hit $+1$ or $-1$. Once it touches the boundary of the hypercube, it is permanently locked. The algorithm drops that dimension and continues walking in the remaining free space.

By carefully managing the number of active constraints relative to the remaining free variables, the authors proved that the walk never gets stuck, successfully converting Spencer's non-constructive proof into a dynamic, linear-algebraic process.

Alternative Paradigms

Following the success of the Edge-Walk framework, researchers developed alternative mathematical toolkits to achieve constructivity.

Lucas Pesenti approached the problem through the lens of regularization, demonstrating that smooth penalty functions can guide an iterative process toward low-discrepancy states without needing explicit geometric constraints. For specific variants like $\ell_2$-discrepancy, Kasper Green Larsen bypassed complex semidefinite programming entirely, utilizing matrix eigendecompositions to efficiently construct colorings with strong hereditary guarantees.

Recently, Laddha et al. synthesized these breakthroughs into a unified algorithmic framework. Their work demonstrates that a single algorithmic approach can recover multiple classic, disparate results in discrepancy theory, proving that the field's foundational existential theorems share a deep, underlying algorithmic structure.

New Frontiers: Noise and Real-Time Decisions

With the basic existential-constructive gap closing, researchers are pushing these algorithmic tools into more challenging environments.

Smoothed Analysis

In worst-case scenarios, problems like the Komlós conjecture—which bounds the discrepancy of a sequence of vectors—remain notoriously difficult. Geometric proofs, such as the partial coloring arguments simplified by Bandeira et al. using Vaaler's theorem, guarantee existence but resist easy algorithmic translation.

To bypass these worst-case bottlenecks, Jiang et al. and Jiang et al. applied smoothed analysis, where inputs are subjected to a small amount of random Gaussian noise. Under this slight perturbation, they proved that prefix and vector discrepancies are exponentially smaller than worst-case bounds, providing a new testing ground for designing efficient constructive algorithms.

Online Discrepancy

In many practical systems, you cannot look at all data points before making a decision. Vectors arrive one by one, and an algorithm must color them immediately without knowing what the future holds.

 Incoming Vector (t) ---> [ Online Algorithm ] ---> Assign +1 or -1 Immediately
                                   |
                           Must keep prefix sums 
                               subgaussian

While non-constructive strategies could prove that well-behaved online sign sequences existed, they required exponential time to compute. Kulkarni et al. resolved this by designing an optimal, polynomial-time online algorithm that maintains subgaussian prefix sums against oblivious adversaries, matching the best known offline bounds and bringing the constructive revolution to real-time data streams.

Key Foundational Work

Near-Optimal Herding (2014) — contributed 1 concept elements to this direction.
Piercing convex sets (1992) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_constructive_existence_proofs_3439bf86,
  title = {non-constructive existence proofs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-constructive-existence-proofs/rdr_3439bf86232b41bdb8f39c77df0c3d2f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_constructive_existence_proofs_3439bf86_v1,
  title = {non-constructive existence proofs},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-constructive-existence-proofs/rdr_3439bf86232b41bdb8f39c77df0c3d2f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake