AF: Medium: Collaborative Research: Circuit Lower Bounds via Projections

AF：中：协作研究：通过投影确定电路下界

• 批准号: 1563155
• 负责人: Rocco Servedio
• 金额: $ 84.15万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-04-01 至 2022-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1563155&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Circuit

Computers play a central role in how we work, play, and communicate with each other in today's world. It is a truism that computers have grown steadily more powerful over the years, but equally important (if not more so) than the amount of sheer computing power available is how efficiently we are able to harness that power. Finding an efficient strategy to solve a given problem (in the language of computer science, an efficient algorithm) can often spell the difference between success and failure. (As an illustrative analogy, consider the task of assembling a large jigsaw puzzle. A poor choice of strategy such as a brute-force approach of trying each pair of pieces against each other may be infeasibly slow, while a cleverer approach such as grouping pieces by their color can be radically more efficient and lead to a feasible solution.) But in order to fully understand the abilities of efficient algorithms, it is crucial to also understand their limits: what is it that efficient algorithms *cannot* do? The field of "computational complexity", which is the subject of the PIs' project, seeks to mathematically prove that certain computational problems do not admit *any* efficient algorithm no matter how long and hard we try to develop one. Such results can have both practical value (by guiding algorithm development away from "dead ends") and deep theoretical significance, as they play a profound role in shaping our fundamental understanding of the phenomenon of computation.The 1980s witnessed exciting progress on a range of Boolean circuit models (a mathematical abstraction of the digital circuits that modern computers are built from) in computational complexity; researchers succeeded in proving many lower bounds establishing that various computational problems have no efficient algorithms in these models. However, further progress slowed significantly after the 1980s. Many of the landmark results obtained in this era were based on the "method of random restrictions", which roughly speaking uses probabilistic arguments to show that Boolean circuits can be dramatically simplified by making certain random substitutions of constant values for input variables. In this project the PIs will intensively investigate an extension of the method of random restrictions which they call the "method of random projections." Rather than simply substituting constant values for input variables, the random projection method additionally identifies groups of variables, "projecting" them all to the same new variable so that they must all take the same value. While the underlying idea is simple, it turns out that this identification of variables helps "maintain useful structure" which is extremely useful for proving lower bounds. In recent work the PIs have successfully used this new "method of random projections" to solve several decades-old problems in Boolean circuit lower bounds and related areas (which in some cases had notoriously resisted progress since the 1980s or 1990s). As the main intellectual goals of the project, the PIs will continue to develop and apply the method of random projections to attack important open problems in Boolean circuit complexity.In addition to the technical goals described above, other central goals of the project are to educate, communicate, and inspire. The PIs will train graduate students through research collaboration, disseminate research results through seminar talks, survey articles and other publications, and continue ongoing outreach activities aimed at increasing interest in and awareness of theoretical computer science topics in a broader population, including presentations at elementary schools.

在当今世界，计算机在我们如何工作、娱乐和相互交流方面发挥着核心作用。不言而喻的是，计算机多年来一直在变得越来越强大，但与可用的绝对计算能力同等重要(如果不是更重要的话)的是，我们能够以多高的效率利用这一能力。找到一种有效的策略来解决给定的问题(在计算机科学的语言中，一种有效的算法)通常会决定成败。(作为一个说明性的类比，考虑一下组装一个大型拼图游戏的任务。一种糟糕的策略选择，比如一对棋子相互较量的蛮力方法，可能会慢得不可行，而更聪明的方法，比如根据棋子的颜色分组，可能会从根本上更有效，并导致可行的解决方案。)但为了充分理解高效算法的能力，了解它们的局限性也是至关重要的：什么是高效算法“不能”做的？“计算复杂性”这一领域是PI项目的主题，它试图从数学上证明，无论我们多么长时间和努力地开发一个有效的算法，某些计算问题都不允许“任何”有效的算法。这样的结果既有实用价值(通过引导算法开发远离“死胡同”)，也有深刻的理论意义，因为它们在塑造我们对计算现象的基本理解方面发挥了深远的作用。20世纪80年代见证了一系列布尔电路模型(构建现代计算机的数字电路的数学抽象)在计算复杂性方面的令人兴奋的进步；研究人员成功地证明了许多下界，确定了各种计算问题在这些模型中没有有效的算法。然而，在1980年代之后，进一步的进展明显放缓。在这个时代获得的许多里程碑式的结果都是基于“随机限制方法”，粗略地说，该方法使用概率论据来表明，通过对输入变量进行某些随机替换，布尔电路可以被极大地简化。在这个项目中，PI将深入调查随机限制方法的一个扩展，他们称之为“随机投影法”。随机投影法不是简单地用常量值代替输入变量，而是额外地识别变量组，将它们全部“投影”到相同的新变量，因此它们必须都取相同的值。虽然基本的想法很简单，但事实证明，这种变量识别有助于“保持有用的结构”，这对于证明下限非常有用。在最近的工作中，PI成功地使用了这种新的“随机投影法”来解决布尔电路下界和相关领域(在某些情况下，自20世纪80年代或90年代以来臭名昭著地阻碍进展)中的数十年问题。作为项目的主要智力目标，PIS将继续开发和应用随机投影的方法来解决布尔电路复杂性中的重要公开问题。除了上述技术目标外，项目的其他中心目标是教育、交流和激励。私人投资机构将通过研究合作培训研究生，通过研讨会演讲、调查文章和其他出版物传播研究成果，并继续开展旨在提高更广泛人群对理论计算机科学专题的兴趣和认识的持续外联活动，包括在小学发表演讲。

项目成果

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces

从少量迹线重建近乎最优的平均情况近似迹线

• 发表时间: 2022
• 期刊: Proceedings of the annual ACMSIAM symposium on discrete algorithms
• 作者: Chen, Xi;De, Anindya;Lee, Chin Ho;Servedio, Rocco A.;Sinha, Sandip
• 通讯作者: Sinha, Sandip