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.

计算机科学发现了各种模型现实世界计算的方法。描述计算的最自然语言也许是位，而这种“布尔”视图主要是该领域。但是，在矩阵或数字等对象上的许多基本计算问题自然用代数的语言表达，这些语言谈到了不同算术系统上的加法和乘法。在这些设置中，解决问题所需的算术操作数量（添加，乘法以及可能的划分）是解决问题的复杂性的一个很好的方法。多年来，计算的代数观点在算法的设计中具有相当大的力量。这些代数算法中有许多驱动现实世界工程；相反，排除问题的良好算法的存在可以推动诸如密码学之类的领域的应用，并导致更具生产力的工程。该项目将探讨如何通过通过“ boolean”位镜头研究核心镜头，研究布尔和代尔布尔和代数复杂性理论来理解代数方法。两种理论之间存在细微的差异。该项目的主要目标是熨除这些微妙之处，并探索一种理论的哪些技术可以扩展到另一种理论。该项目的更广泛的影响包括PI和DODOC的新课程，培训研究生，公众的理论倡导以及由PI和PostDoc共同组织的社区建设活动。一类重要类别的算法技术来自代数，这些技术通常来自整体上，高级现有的设置。但是，我们不完全了解代数工具包的力量，在这方面存在主要的开放问题，这些问题在代数几何和复杂性理论中提出了基本挑战。该项目的三个主要研究线程是：（1）通过算术方式查看布尔问题的功能下限，（2）在布尔值复杂性中“自然证明”障碍的代数类似物，以在当前技术中寻找基本限制的基本限制，以构成对代数计算的方法，以实现Algebraic Alle new ealger new ealgerbraic方法，以实现Algebraic ne eLgeraic ne eLgeraic方法。令人满意。功能下限的线程将应用后DOC的最新见解，以令人惊讶的代数框架中表征了一类精心研究且有趣的布尔问题。自然证明类似物将研究PI和PostDoc提出的“代数伪函数”的新概念，了解如何从代数中查看某些密码原始词。代数算法设计线程将从PI最近的概率非相互作用证明系统的工作中进行，以反驳不满意的布尔公式，试图“降低”证明系统或了解所涉及的障碍。