CAREER: Boolean Function Analysis and Its Applications in Computer Science

这个项目致力于布尔函数分析的新研究。布尔函数是计算机科学中研究最多的组合对象之一，理论计算机科学的各个领域都对其感兴趣，包括但不限于量子计算、复杂性理论和学习理论。由于计算机科学中的所有计算都由布尔值表示，因此布尔函数通常用于分析计算过程。在这个项目中，研究者的目标是在布尔函数分析的几个核心开放问题上取得进展，并与计算机科学的其他研究领域建立联系。具体来说，研究者主要关注以下三个问题。低次有界布尔函数影响变量的Aaronson-Ambainis猜想。小尺寸析取范式（dnf）的傅里叶稀疏性的Mansour猜想。关于集合系统结构的向日葵猜想。Aaronson-Ambainis猜想与量子计算有关。它捕捉到量子查询何时可以显著加快经典计算速度。曼苏尔猜想与机器学习理论有关。作为推论，给出了一种有效的dnf不可知学习算法。向日葵猜想与极值组合有关，是数学研究的一个活跃领域。该项目的教育计划包括课程开发与研究相结合。将有一至两名博士生参与该项目，作为其博士培养的一部分。研究者还将开设一门布尔函数分析的课程。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.