Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere

Inspired by the boolean discrepancy problem, we study the following optimization problem which we term $\text{textsc}SphericalDiscrepancy$: given $m$ unit vectors $v_1,\dots ,v_m$, find another unit vector $x$ that minimizes ${\max }_i⟨x,v_i⟩$. We show that $\text{textsc}SphericalDiscrepancy$ is APX-hard and develop a multiplicative weights-based algorithm that achieves optimal worst-case error bounds up to lower order terms. We use our algorithm to give the first non-trivial lower bounds for the problem of covering a hypersphere by hyperspherical caps of uniform volume at least $2^{-o(\sqrt{n})}$. We accomplish this by proving a related covering bound in Gaussian space and showing that in this $\mathit{\text{large}}\mathit{\text{cap}}\mathit{\text{regime}}$ the bound transfers to spherical space. Up to a log factor, our lower bounds match known upper bounds in the large cap regime.