Algorithms Beyond the Union Bound: Polynomial Optimization and Discrepancy Theory

The union bound is a classical tool in the probabilistic method for proving the existence of objects with extremal features by showing that a random object satisfies each feature with high probability. This approach has powered major results spanning theoretical computer science, combinatorics, random matrix theory, and statistical physics — such as the existence of graph sparsifiers, satisfying assignments to constraint satisfaction problems, and low-energy configurations in spin glass models. However, the union bound ignores correlations between different features, and thereby often leads to suboptimal results in these applications. This thesis presents an alternative approach: proving existence by designing and analyzing algorithms that construct the desired objects. We show that all the above problems can be formulated as minimizing either low-degree polynomials or linear-image norms in high dimensions. For these objectives, we analyze algorithms inspired by continuous optimization. In the first part, we propose an orthogonal representation for first-order algorithms optimizing random quadratic polynomials using Fourier analysis. We show that in the high-dimensional limit, these algorithms can be analyzed by tracking their dynamics in a tree basis. This reframes random polynomial optimization as a combinatorial problem, which we explicitly solve in some cases. Our approach also yields the first direct justification in this setting of the heuristic cavity method from physics. The second part extends the approach to general polynomial optimization. We introduce a multiscale union bound argument for random tensors, extending results of Friedman and Wigderson on the spectral gap of random hypergraphs. We further present a new rounding scheme for semidefinite programming relaxations, leading to improved approximations for homogeneous cubic optimization and the Max-3-Sat problem. In the third part, we design an algorithm for minimizing norms of linear functions via Newton’s method applied to a regularized objective function. By varying the regularizer, we recover and generalize foundational results in discrepancy theory. This framework yields an improved bound in Spencer’s classical result from the 1980s, and establishes that the Beck–Fiala and Komlós conjectures hold for a new class of pseudorandom instances. Together, these results show that algorithms can not only match, but also exceed the power of probabilistic arguments for finding extremal objects.