CaltechTHESIS
A Caltech Library Service

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.

Item Type: Thesis (Dissertation (Ph.D.))
Subject Keywords: Functional analysis; Approximation theory; Discretization inequalities; Learning theory; Property testing; Circuit theory
Degree Grantor: California Institute of Technology
Division: Engineering and Applied Science
Major Option: Computing and Mathematical Sciences
Awards: Bhansali Family Doctoral Prize in Computer Science, 2025.
Thesis Availability: Public (worldwide access)
Research Advisor(s):
  • Umans, Christopher M.
Thesis Committee:
  • Schulman, Leonard J. (chair)
  • Tamuz, Omer
  • Tropp, Joel A.
  • Umans, Christopher M.
Defense Date: 29 May 2025
Non-Caltech Author Email: joseph.slote (AT) gmail.com
Funders:
Funding Agency Grant Number
Simons Foundation Investigator Award (Chris Umans) UNSPECIFIED
Record Number: CaltechTHESIS:06082025-235351698
Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:06082025-235351698
DOI: 10.7907/grjv-rz74
Related URLs:
URL URL Type Description
https://doi.org/10.19086/da.137968 DOI A dimension-free Remez-type inequality on the polytorus
https://doi.org/10.1016/j.aim.2024.109824 DOI Bohnenblust–Hille inequality for cyclic groups
https://doi.org/10.4230/LIPIcs.ITCS.2024.69 DOI Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality
https://arxiv.org/abs/2411.12730 arXiv Testing classical properties from quantum data
https://doi.org/10.1007/s00222-024-01306-9 DOI Dimension-free discretizations of the uniform norm by small product sets
https://doi.org/10.4230/LIPIcs.ITCS.2024.92 DOI Parity vs. AC0 with Simple Quantum Preprocessing
https://arxiv.org/abs/2406.08509 arXiv Noncommutative Bohnenblust--Hille Inequality for qudit systems
ORCID:
Author ORCID
Slote, Joseph Alfred 0000-0002-6363-7821
Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code: 17423
Collection: CaltechTHESIS
Deposited By: Joseph Slote
Deposited On: 09 Jun 2025 21:07
Last Modified: 14 Nov 2025 21:12

Thesis Files

[img] PDF - Final Version
See Usage Policy.

1MB

Repository Staff Only: item control page