CAREER: New Challenges in Analysis of Boolean Functions

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.