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

Citation

Slote, Joseph Alfred (2025) Discrete Harmonic Analysis and its Applications to Testing, Learning, and Complexity. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/grjv-rz74. https://resolver.caltech.edu/CaltechTHESIS:06082025-235351698

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.