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

AF:Small:布尔复杂性理论对代数方法的限制

• 批准号: 1741638
• 负责人: Ryan Williams
• 金额: $ 7.06万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-01-20 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1741638&HistoricalAwards=false
• 关键词: AF; Small; Limitations; Algebraic; Methods

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.

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