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

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

• 批准号: 1617580
• 负责人: Ryan Williams
• 金额: $ 10.99万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2017-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1617580&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最近关于驳斥不可满足布尔公式的概率非交互证明系统的工作出发，试图要么使证明系统去随机化，要么理解所涉及的障碍。