CAREER: New Challenges in Analysis of Boolean Functions

计算机科学中的许多领域都涉及表现出良好的局部一致性属性的大型对象。例如，考虑一个编码的消息已经通过一个不完美的通信信道，因此，被轻微损坏。能否有效纠正？通常情况下，查看小窗口-即编码消息中连续字母的小块-是完全有意义的，并且可以解码（因为通道没有破坏它们），除了一些字母被破坏的窗口。尽管只影响少数窗口，但这些损坏可能导致对消息意图的完全误解：想象英语中的一个句子，并将其与其中单词“yes”被替换为单词“no”的相同句子进行比较。为了处理这种情况，人们希望找到方法来确保可以完美、有效地恢复未损坏的消息。有没有一种方法可以在好的窗口中使用强的局部递归，以及编码消息的整体全局结构，从而以一种有效的方式进行这种恢复？为了通过教育进一步扩大研究的影响力，该项目包括出版临时材料和在一家研究机构开展涉及多个训练营的教育计划等活动。设计具有这种“局部恢复属性”的对象，通常被称为“局部到全局现象”，是理论计算机科学的主要目标之一。布尔函数分析（也称为离散傅立叶分析）通常是在复杂性理论、学习理论、纠错码和属性测试等领域建立此类结果的重要工具。在这些上下文中，特别有趣的是被称为扩展、小集合扩展和超收缩的概念，它们断言手中的对象是非常好的连接，因此其中的“不可修复的损坏”永远不会包含在“小窗口”中。事实上，扩张、小集合扩张和超收缩性已经被用来证明理论计算机科学中上述领域的大量重要结果。然而，有一些重要的应用需要处理不具有如此强的膨胀特性的对象。该项目旨在扩展该理论，以应对这些更具挑战性的对象，并利用它在复杂性理论、纠错码、概率可检验证明等关键问题上取得进展。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

Many areas in computer science deal with large objects that exhibit good local consistency properties. Consider, for example, that an encoded message has been passed through an imperfect communication channel and, as a result, was slightly corrupted. Can it be efficiently corrected? Often, looking at small windows – namely small chunks of consecutive letters in the encoded message— makes complete sense, and they can be decoded (as the channel did not corrupt them), except for a few windows in which some letter has been corrupted. Despite affecting only a small number of windows, these corruptions may lead to a complete misinterpretation of the intention of the message: imagine a sentence in the English language, and compare it with the same sentence in which the word "yes" has been replaced with the word "no". To handle such cases, one would like to find ways to ensure that a perfect, efficient recovery of the uncorrupted message is possible. Is there a way to use the strong local consistencies in the good windows and the overall global structure of the encoded message to allow such recovery in an efficient way? To further the research's impact through education, the project includes activities such as the publication of expository materials and an educational program at a research institute involving several bootcamps.Designing objects with this type of "local recovery property," which often goes by the name "local to global phenomenon", is one of the prime objectives of theoretical computer science. The field of Analysis of Boolean functions (also known as discrete Fourier analysis) is often a vital tool in establishing such results in areas including complexity theory, learning theory, error correcting codes, and property testing. In these contexts, of particular interest are notions known as expansion, small-set expansion, and hypercontractivity, asserting that the object in hand is very well connected so that "unfixable corruptions" in it can never be contained in "small windows." Indeed, expansion, small set expansion, and hypercontractivity have been used to prove a large number of important results in theoretical computer science in the areas mentioned above and more. There are significant applications, however, that require working with objects that do not possess such strong expansion properties. This project aims to extend the theory to deal with these more challenging objects and to use it to make progress in crucial questions in complexity theory, error-correcting codes, probabilistically checkable proofs, and more.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.