Discrete Approximation

NSF Award Search · 01002627DB NSF RESEARCH & RELATED ACTIVIT · $299,999 · view on nsf.gov ↗

Abstract

Modern data science, quantum computation, and high-dimensional probability rely on mathematical tools for understanding functions of many yes/no variables and their continuous analogues. This project studies such functions on the discrete cube and in Gaussian space, where approximation, learning, randomness, and boundary structure can be analyzed precisely. The work addresses basic questions about how much information is needed to learn a low-complexity function, how well complicated functions can be approximated by simple polynomials, and how the shape of a high-dimensional set controls its boundary. These questions are central to mathematics and also inform learning theory and quantum computing. This project promotes the progress of science and advances national prosperity and welfare by strengthening foundations for reliable computation, high-dimensional data analysis, and artificial intelligence. The project also supports education and workforce development through training of graduate students and postdoctoral researchers, summer schools and research programs for early-career researchers, and dissemination through seminars, webinars, lecture notes, and preprints. The investigator develops a unified program in analysis on discrete and Gaussian spaces, using semigroup methods, Fourier analysis on the Hamming cube, hypercontractivity, and sharp inequalities. The project seeks sharper Bohnenblust-Hille and hypercontractive inequalities, with applications to PAC learning of low-degree Boolean functions, learning with small spectral support, polynomial threshold functions, and the Aaronson-Ambainis conjecture in quantum query complexity. It develops Jackson- and Poincare-type approximation theorems with dimension-independent bounds and transfers discrete approximation principles to Gaussian weighted approximation. It pursues sharp isoperimetric and influence inequalities, including progress on the Kahn-Park conjecture and the remaining range of Weissler's complex

Key facts

NSF award ID
2554183
Awardee
University of California-Irvine (CA)
SAM.gov UEI
MJC5FCYQTPE6
PI
Paata Ivanisvili
Primary program
01002627DB NSF RESEARCH & RELATED ACTIVIT
All programs
Artificial Intelligence (AI), QUANTUM INFORMATION SCIENCE
Estimated total
$299,999
Funds obligated
$299,999
Transaction type
Standard Grant
Period
08/15/2026 → 07/31/2029