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

计算机科学已经发现了各种方法来模拟真实世界的计算。也许描述计算的最自然的语言是位，这种“布尔”观点主导了这个领域。然而，许多关于矩阵或数字等对象的基本计算问题都是用代数语言自然表达的，代数语言涉及不同算术系统的加法和乘法。在这些设置中，解决问题所需的算术运算（加法、乘法和可能的除法）的数量是衡量问题复杂性的一个很好的指标。多年来，计算的代数观点在算法的设计中发挥了相当大的作用。这些代数算法中的许多都推动了现实世界的工程;相反，排除一个问题的好算法的存在可以推动密码学等领域的应用，并导致更富有成效的工程。本项目将探索如何通过“布尔”的比特透镜来检查核心问题，研究布尔和代数复杂性理论之间的关系，从而理解代数方法。这两种理论之间存在微妙的差异;本项目的主要目标是解决这些微妙之处，并探索一种理论中的哪些技术可以扩展到另一种理论。该项目更广泛的影响包括PI和博士后设计新课程，培训研究生，在公众中宣传理论，以及PI和博士后共同组织的社区建设活动。一类重要的算法技术来自代数，这些技术通常出现在广泛的，高影响力的环境中。然而，我们并不完全理解的权力的代数工具包，并有重大的开放问题，在这方面提出了根本性的挑战，代数几何和复杂性理论。该项目的三个主要研究方向是：（1）布尔问题的函数下界，以算术的方式看待它们，（2）布尔复杂性中“自然证明”障碍的代数模拟，寻找当前代数计算推理技术的基本限制，以及（3）设计基本问题算法的新代数方法，如布尔可满足性。函数下界的线程将应用博士后的最新见解，在一个令人惊讶的代数框架中描述一类经过充分研究和有趣的布尔问题。自然证明模拟将研究PI和博士后提出的“代数伪随机函数”的新概念，了解如何从代数角度看待某些密码原语。代数算法设计线程将从PI最近关于概率非交互式证明系统的工作中进行，用于反驳不可满足的布尔公式，试图“去随机化”证明系统或理解所涉及的障碍。

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.