CAREER: Boolean Function Analysis and Its Applications in Computer Science

University Of Southern California, Los Angeles CA

Investigators

Abstract

This project is dedicated to new research on the analysis of Boolean functions. Boolean functions are some of the most studied combinatorial objects in computer science, with interest from diverse areas of theoretical computer science including but not limited to quantum computing, complexity theory, and learning theory. Since all computations in computer science are represented by Boolean values, Boolean functions are commonly used to analyze the computational process. In this project, the investigator aims to make progress on several central open problems in Boolean function analysis and build connections to other research areas in computer science. Specifically, the investigator focuses on the following three problems. 1. The Aaronson-Ambainis Conjecture on influential variables of low-degree bounded Boolean functions. 2. Mansour’s Conjecture on the Fourier sparsity of small-size Disjunctive Normal Forms (DNFs). 3. The sunflower conjecture on the structure of set systems. The Aaronson-Ambainis Conjecture has connections to quantum computing. It captures when quantum queries can speed up classical computation significantly. Mansour's Conjecture has connections to machine-learning theory. As a corollary, it gives an efficient agnostic learning algorithm for DNFs. The sunflower conjecture connects to extremal combinatorics, which is an active research area of mathematics. The project’s educational plans including course development are integrated with the research. One or two PhD students will participate in this project as part of their PhD training. The investigator will also create a course about Boolean-function analysis. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.