Discrete Harmonic Analysis and its Applications to Testing, Learning, and Complexity

Author: Slote, Joseph Alfred

Year: 2025

Degree: Dissertation (Ph.D.)

Advisor: Umans, Christopher M.

Committee Members: Schulman, Leonard J.; Tamuz, Omer; Tropp, Joel A.; Umans, Christopher M.

Option: Computing and Mathematical Sciences

DOI: 10.7907/grjv-rz74

Abstract

This thesis consists of two parts. In Part I we present a new class of norm discretization inequalities suited for low-degree polynomials in many dimensions, with applications to discrete harmonic analysis and to quantum and classical learning theory.

Discretization inequalities (of Bernstein type) control the supremum norm of polynomials f by their supremum norms over certain finite subsets T of the domain. Unlike earlier multivariate Bernstein-type discretization inequalities we establish dimension-free comparisons for simple and generic T, such as product sets T=S₁ × ⋅⋅⋅ × Sₙ for Sⱼ's consisting of well-spread points in R or C, in exchange for a constant that grows with deg(f).

Our results also introduce the notion of "individual degree"—the maximum degree of f in any one variable—as a fundamental parameter for discretization inequalities: we show for the first time that dimension-free discretizations of the uniform norm are possible for T with cardinality independent of deg(f), provided f has bounded individual degree.

Our work offers a new, high-dimensional perspective on discretization inequalities and yields several new results in analysis on the hypergrid (i.e., products of cyclic groups), including Bohnenblust–Hille-type inequalities, dimension-free supremum norm bounds on level-k Fourier projections, and junta theorems. These estimates in turn provide the key analytic tools for extending recent breakthroughs in learning low-degree functions to the hypergrid and to its quantum analogue, local observables on K-level qudit systems.

In Part II we apply ideas from analysis of Boolean functions to study other aspects of (quantum) computation: circuit complexity and property testing.

First, we introduce and study a deceptively simple model of constant-depth quantum circuits and begin the project of proving bounds on its capabilities, ultimately drawing on connections to nonlocal games and notions of approximate degree.

Second, we introduce a new access model for property testing, quantum data, which allows for ultrafast testing algorithms where classical data provably yields no fast testers—such as for monotonicity, symmetry, and triangle-freeness.

Files