Many tasks ask us to split a set of items into two halves that are balanced with respect to every test in a large family. Examples include treatment/control assignment balanced across covariate slabs, thinning a dataset so that a small sample keeps every range average, and halving steps in herding-style sampling. This is discrepancy minimization: assign each item a sign $\pm 1$ so that for every set in a family the signed sum is close to zero. The best practical algorithms reach that balance by iterative partial coloring. They repeatedly fix the signs of about half of the still-undecided items through a slow random walk on fractional values, then recurse on the rest. These algorithms are static. If one item is inserted or deleted, the whole computation is redone. Under any reasonable notion of a dynamic data structure, a maintained balanced coloring therefore costs either a full recomputation per change or a fall back to random signs, which are roughly $\sqrt{n}$-times worse on structured families.
We propose to make the last stage of iterative partial coloring into a buffer. The structure deliberately never finishes the coloring. It keeps a small reserve of items whose values are still fractional, strictly between $-1$ and $+1$. When an item is deleted or inserted, a short local walk on the reserve repairs the damage, so the decided items are never recomputed. The size of the reserve is a single tunable dial between update cost and query quality. A large reserve absorbs many updates cheaply but makes the final rounding at query time noisier. A small reserve gives near-static quality but needs frequent rebuilds. This is the classical query-update tradeoff of dynamic data structures, here applied to a combinatorial object no one has made dynamic.
Core Claim
The claim is that a hierarchical partial coloring with a fractional reserve of size $r$ can maintain a coloring of an evolving point set. The coloring would stay within a constant factor of the static guarantee of Fast Discrepancy Minimization with Hereditary Guarantees, plus an additive rounding term. The amortized update cost would be polylogarithmic in $n$ times the cost of a walk on $r$ coordinates. Concretely, writing $D_{\text{static}}(n)$ for the discrepancy Larsen's algorithm achieves on an $m$-set, $n$-item instance, we target
$$ \max_{S}\Big|\sum_{u\in S} x_u\Big| \;\le\; C\, D_{\text{static}}(n) \;+\; O\big(\sqrt{r\log m}\big), $$
where $x$ is the coloring returned at query time after the reserve is randomly rounded. The second term is the standard Chernoff bound for independently rounding $r$ fractional coordinates against $m$ sets. Choosing $r \approx D_{\text{static}}^2/\log m$ makes the rounding term no larger than the static guarantee. Larger $r$ buys cheaper updates at a stated cost in balance. To our knowledge this would be the first dynamic data structure for combinatorial discrepancy with sublinear update time and a quality guarantee tied to hereditary discrepancy.
Positioning Against Prior Work
The method draws on three sources. The first is Larsen's algorithm, which supplies the static engine. Its ProjectToSmallRows step projects away the large-eigenvalue directions of the set-incidence matrix, and its Edge-Walk partial coloring fixes coordinates while keeping row sums small. The algorithm runs in $O(mn^2\lg(2+m/n)+n^3)$ time with discrepancy $O(\lg n\cdot\lg^{3/2}m\cdot\text{herdisc}(A))$, where herdisc is the worst discrepancy over all column subsets. We reuse this engine unchanged. What we add is the dynamic layer: which levels to rebuild, and the reserve that prevents rebuilds.
The second source is the dynamic nibble edge-coloring of Nibbling at Long Cycles. It shows that a round-based partial process with pre-fixed randomness has constant expected recourse per update, meaning few edges change color. It motivates our bet that partial processes are naturally stable under updates. Its query, however, is a trivial lookup of one edge's color, and its guarantee depends on high-degree concentration. Discrepancy has neither a local constraint graph nor concentration in that sense, so we cannot reuse its analysis, only its intuition.
The third source is the dynamic fractional-matching rounding of Deterministic Rounding of Dynamic Fractional Matchings. It keeps a fractional solution and rounds lazily. This is the closest structural precedent for keeping the reserve fractional, but it is specific to matchings.
Two results bound what we can hope for. First, Optimal Online Discrepancy Minimization shows that with zero recourse, an algorithm that signs arriving vectors irrevocably can match offline $O(\sqrt{\log T})$ against an oblivious adversary. Its construction runs in $\exp(T^{CnT})$ time, and against adaptive adversaries the bound degrades to $\Omega(\sqrt{T})$. We therefore commit to an oblivious update sequence and treat recourse as a resource to be spent. Second, the buffering limits in Dynamic External Hashing: The Limit of Buffering and Dynamic Indexability and the Optimality of B-Trees rest on an indivisibility assumption, where records are atomic. Our fractional reserve is precisely a divisible buffer. We do not claim it breaks those bounds, which concern different problems. We note it as the reason a buffer can work here at all.
The motivating application comes from Near-optimal Herding. It reduces mean-tracking sampling to a permutation problem solved by iterative partial coloring, with error $O(\sqrt{d}\log^{2.5}|X|/t)$. That construction is static. The dynamic sampling indexes DIPS and BUS/WIRS-BUS handle updates in $O(1)$ but draw independent samples. Our structure is a step toward balanced samples from changing data. We treat this as a downstream test, not the main claim.
Research Program
The structure organizes items into geometrically sized blocks, as in the logarithmic method of dynamic data structures. Each block stores three things. The first is its own partial-coloring hierarchy, which records the level at which each item's sign was fixed. The second is the projection used at each level. The third is a reserve of at most $r$ fractional coordinates held back from the final level. A query that needs a full coloring rounds the reserve independently. A query asking for the signed sum of a range evaluates the current fractional vector directly.
An insertion places the new item in the smallest block's reserve at value $0$. Insertions cause block merges in the usual way, but a merge restarts the walk only on the union of the two reserves and the top level. Deeper levels are kept.
A deletion of an already-decided item with sign $s$ shifts every set containing that item by $-s$. The repair releases one or two decided items with matching sign from the same block back into the reserve. It then runs Larsen's Edge-Walk on the enlarged reserve, restricted to the subspace already used at that block's last level, until the reserve returns to size $r$. A block is rebuilt only when its accumulated drift exceeds a threshold tied to $D_{\text{static}}$.
The analysis has two parts, and we expect the second to be the hard one. The first part shows that the walk on the reserve contracts the drift a deletion introduces. This should follow from the same small-row-norm property after projection that makes the static walk work. The second part bounds how often blocks must be rebuilt as a function of $r$. That bound gives the update side of the tradeoff, and our working conjecture is amortized cost about $(n_{\text{block}}/r)\cdot T_{\text{walk}}(r)$ per update. We will also ask whether a matching lower bound exists. The natural route is the encoding technique of The cell probe complexity of dynamic range counting, applied to range-sum queries on the maintained signs. Because the structure chooses its own weights, the reduction is not immediate. We list this as a stretch goal rather than a promised result.
Baselines
The naive reference point is an independent uniformly random sign per item. It has $O(1)$ update and zero recourse, and on structured families its discrepancy is about $\sqrt{n\log m}$. We run it with the same update sequences and report its discrepancy distribution over seeds. Any method that fails to beat it by a wide margin on corner and halfspace families is not worth its cost. The file gives no reported number for random colorings on a dynamic workload. We will measure it ourselves.
The strongest quality baseline is full recomputation with Larsen's static algorithm after every $k$ updates, for several $k$, including $k=1$ as an oracle. The only reported number on Lacuna is static. On $4000\times4000$ uniform $\pm1$ matrices, the discrepancy is "roughly 10 times smaller than a single random sample and 4 times smaller than multiple random samples run for the same duration" (Fast Discrepancy Minimization with Hereditary Guarantees). We use our reimplementation of that algorithm both as this baseline and as the engine inside our structure, so code-level speed differences cancel. We count it as beaten if, at equal total wall-clock over a workload, our structure reaches discrepancy within 1.5× of the $k=1$ oracle. Periodic rebuilding at the same time budget must do worse.
The strongest structural baseline is the logarithmic method applied to finished static colorings. Blocks of size $2^j$ are each colored once by Larsen's algorithm, and their colorings are concatenated. Insertions are cheap. Deletions are handled by rebuilding the block they hit. It receives the same block sizes, engine, and time budget as our method.
The ablation that isolates the key ingredient is our structure with $r=0$. In that version every deletion triggers a local walk on freshly released items, but nothing is ever held fractional. Comparing $r=0$ to tuned $r>0$ tests whether the reserve is doing the work or whether warm-started local repair alone suffices.
Why not just…?
Why not just use the logarithmic method on static colorings? This is the serious competitor. For families whose hereditary discrepancy grows polynomially, such as halfspaces at $O(n^{1/4})$, the block discrepancies form a geometric series, and the concatenation is already within a constant of static. For insertion-only workloads on such families, we expect it to match us, and we will report that honestly. It loses in two places. On polylogarithmic families like 2D corners ($O(\log^{2.5}n)$), the sum over $\log n$ blocks costs an extra logarithmic factor. Under deletions, the restriction of a finished coloring to the surviving items carries no guarantee: hereditary discrepancy promises that a good coloring of the subset exists, not that the old one is still good. The mixed insert/delete experiment on corners decides whether our method is needed.
Why not just re-run Larsen's walk warm-started from the old coloring? A warm start on a finished coloring has nowhere to move. Every coordinate sits at $\pm1$, and the walk can only reopen coordinates by explicitly un-fixing them. Choosing which to un-fix, and how many, is exactly the reserve design. The $r=0$ ablation is this alternative with the cheapest un-fixing rule. If it matches the tuned reserve, the reserve is unnecessary and we would simplify the method to "local un-fix and re-walk."
Why not just rebuild periodically and accept stale balance between rebuilds? Between rebuilds, deletions push each affected set's sum by one per deletion. Staleness therefore grows linearly in the number of updates, while the target discrepancy grows polylogarithmically on corners. Periodic rebuilding is run at matched compute in the Baselines comparison. The drift-over-time plot will show whether its discrepancy sawtooth exceeds ours at every point of the budget curve.
Proposed Experiments
The primary benchmarks are the three families from Larsen's evaluation: uniform $\pm1$ matrices, 2D corner (dominance) matrices, and 2D halfspace matrices. All start at $4000\times4000$. Each is turned into a dynamic workload by an oblivious sequence of item insertions and deletions, in mixes of 100/0, 70/30 and 50/50, over $10n$ operations.
For each method we record three metrics: discrepancy (maximum absolute range sum) after each operation, wall-clock and walk steps per update, and recourse (signs changed per update). The central figure plots time per update against discrepancy as $r$ varies, overlaid with the baselines' operating points. A second figure checks the predicted $\sqrt{r\log m}$ rounding term against the measured gap between fractional and rounded discrepancy.
To test scaling, we use the Stanford Dragon scan (3.6M points) with random halfspace ranges, subsampled to sizes where the static engine is still feasible. The point is to see whether amortized update cost grows polylogarithmically, as conjectured, or polynomially.
As a downstream check, we use the halving coloring to thin a dynamically weighted set drawn from the USA road network weights used by BUS/WIRS-BUS. We compare mean-estimation error of the balanced half against BUS's independent samples at equal sample size. The file reports BUS speedups but no estimation-error number, so no reported result was found on Lacuna for this metric, and we measure both.
The decisive outcomes are as follows. If on 2D corners under 50/50 updates the tuned reserve stays within 1.5× of the rebuild-every-update oracle at a small fraction of its time, and beats both the logarithmic method and the $r=0$ ablation, the claim stands. If the logarithmic method matches it there, the contribution shrinks to a negative result about where reserves help, and we would report it as such.
References
- Fast Discrepancy Minimization with Hereditary Guarantees
- Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
- Deterministic Rounding of Dynamic Fractional Matchings
- Optimal Online Discrepancy Minimization
- Dynamic external hashing: the limit of buffering
- Dynamic Indexability and the Optimality of B-Trees
- Near-optimal Herding
- DIPS: Optimal Dynamic Index for Poisson πps Sampling
- Efficient Dynamic Weighted Set Sampling and Its Extension
- The cell probe complexity of dynamic range counting