AF:Small:Limitations on Algebraic Methods via Boolean Complexity Theory

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Computer science has discovered a variety of ways to model real-world computing. Perhaps the most natural language for describing computation is that of bits, and this "Boolean" view predominates the field. However, many fundamental computation problems on objects such as matrices or numbers are naturally expressed in the language of algebra, which speaks of addition and multiplication over different arithmetic systems. In those settings, the number of arithmetic operations (additions, multiplications, and possibly divisions) needed to solve the problem is a good measure for the complexity of the problem. Over the years, the algebraic view of computation has wielded considerable power in the design of algorithms. Many of these algebraic algorithms drive real-world engineering; conversely, ruling out the existence of good algorithms for a problem can drive applications in fields like cryptography, and lead to more productive engineering. This project will explore how algebraic methods can be understood by examining the core problems through the "Boolean" lens of bits, studying relationships between Boolean and algebraic complexity theory. There are subtle differences between the two theories; a major goal of this project is to iron-out these subtleties, and explore which techniques from one theory can be extended to the other. The broader impacts of the project include the design of new courses by the PI and postdoc, training graduate students, theory advocacy in the general public, and community-building activities co-organized by the PI and postdoc. An important class of algorithmic techniques come from algebra, and these techniques often arise in broad, high-impact settings. However, we do not fully understand the power of the algebraic toolkit, and there are major open problems in this regard which present fundamental challenges in algebraic geometry and complexity theory. Three major research threads of this project are: (1) functional lower bounds on Boolean problems, by viewing them in an arithmetic way, (2) an algebraic analogue of the "Natural Proofs" barrier in Boolean complexity, searching for fundamental limitations in the present technology for reasoning about algebraic computation, and (3) new algebraic approaches for designing algorithms for fundamental problems such as Boolean Satisfiability. The thread of functional lower bounds will apply recent insights of the postdoc, characterizing a class of well-studied and interesting Boolean problems in a surprising algebraic framework. The Natural Proofs analogue will study a new notion of "algebraic pseudorandom functions" proposed by the PI and postdoc, understanding how certain cryptographic primitives can be viewed algebraically. The algebraic algorithm design thread will proceed from recent work of the PI on probabilistic non-interactive proof systems for refuting unsatisfiable Boolean formulas, attempting to either "de-randomize" the proof system or understand the obstacles involved.