  Discrepancy theory provides powerful tools for producing higher-quality
objects which "beat the union bound" in fundamental settings throughout
combinatorics and computer science. However, this quality has often come at the
price of more expensive algorithms. We introduce a new framework for bridging
this gap, by allowing for the efficient implementation of discrepancy-theoretic
primitives. Our framework repeatedly solves regularized optimization problems
to low accuracy to approximate the partial coloring method of [Rot17], and
simplifies and generalizes recent work of [JSS23] on fast algorithms for
Spencer's theorem. In particular, our framework only requires that the
discrepancy body of interest has exponentially large Gaussian measure and is
expressible as a sublevel set of a symmetric, convex function. We combine this
framework with new tools for proving Gaussian measure lower bounds to give
improved algorithms for a variety of sparsification and coloring problems.
  As a first application, we use our framework to obtain an $\widetilde{O}(m
\cdot \epsilon^{-3.5})$ time algorithm for constructing an
$\epsilon$-approximate spectral sparsifier of an $m$-edge graph, matching the
sparsity of [BSS14] up to constant factors and improving upon the
$\widetilde{O}(m \cdot \epsilon^{-6.5})$ runtime of [LeeS17]. We further give a
state-of-the-art algorithm for constructing graph ultrasparsifiers and an
almost-linear time algorithm for constructing linear-sized degree-preserving
sparsifiers via discrepancy theory; in the latter case, such sparsifiers were
not known to exist previously. We generalize these results to their analogs in
sparsifying isotropic sums of positive semidefinite matrices. Finally, to
demonstrate the versatility of our technique, we obtain a nearly-input-sparsity
time constructive algorithm for Spencer's theorem (where we recover a recent
result of [JSS23]).
