AF: Medium: Collaborative Research: Information Compression in Algorithm Design and Statistical Physics

AF：媒介：协作研究：算法设计和统计物理中的信息压缩

• 批准号: 1514164
• 负责人: Eric Allender
• 金额: $ 46.13万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1514164&HistoricalAwards=false
• 关键词: AF; Medium; Collaborative; Research; Information

The existence of connections between probabilistic algorithms, statistical physics and information theory has been known for decades and has yielded a number of unexpected breakthroughs. Recent discoveries of the PIs and other researchers give clear indications that these connections go much deeper than previously thought. A key new idea is the realization that stochastic local search algorithms can be judged by their capacity to compress the randomness they consume, with convergence following as a consequence of compressibility. Further exploration of this idea is expected to have significant impact, both conceptual and technical, in multiple scientific fields. This includes algorithm design by information theoretic methods, the study of phase transitions in statistical mechanical systems based on information bottleneck arguments, and non-constructive proofs of existence of combinatorial objects. The project will offer a wide range of research opportunities at various levels of sophistication for graduate and undergraduate students in three state universities.Information compression arguments have recently found striking applications in computer science and combinatorics. A glowing example is Moser's proof of the algorithmic Lovasz Local Lemma, which suggested an entirely new way of reasoning about randomized algorithms. Inspired by the work of Moser, one of the PIs with a collaborator has very recently created a general framework for analyzing stochastic local search algorithms using information compression. The framework is purely algorithmic, completely bypassing the Probabilistic Method. Besides helping to analyze the running times of existing algorithms it can also be used as a powerful new tool for designing novel, non-obvious randomized algorithms. The proposed research further develops this framework with the aim of unearthing completely new applications in computer science and combinatorics, while establishing mathematically rigorous connections to statistical physics. Concrete examples of such applications to be investigated include new tools for bounding the mixing time of Markov chains and algebraic connections between randomized algorithms and the classical theory of phase transitions in statistical physics.

概率算法，统计物理学和信息理论之间存在连接的存在已有数十年了，并产生了许多意外的突破。 PIS和其他研究人员的最新发现清楚地表明，这些联系比以前想象的要深得多。一个关键的新想法是认识到，随机局部搜索算法可以通过压缩其消耗的随机性的能力来判断，并且由于可压缩性而随之而来。在多个科学领域，对该想法的进一步探索有望产生概念和技术的重大影响。这包括通过信息理论方法的算法设计，基于信息瓶颈参数的统计机械系统中的相变的研究以及组合对象存在的非构造性证明。该项目将为三个州立大学的研究生和本科生提供各种成熟水平的研究机会。信息压缩论证最近在计算机科学和组合学方面发现了惊人的应用。一个发光的例子是Moser证明算法Lovasz本地引理，这提出了一种全新的关于随机算法的推理方式。受Moser的工作启发，其中一位与合作者的PI最近创建了一个通用框架，用于使用信息压缩分析随机的本地搜索算法。该框架纯粹是算法，完全绕过了概率方法。除了帮助分析现有算法的运行时间外，它还可以用作设计新颖的，非客观的随机算法的强大新工具。拟议的研究进一步开发了该框架，目的是在计算机科学和组合技术中发掘全新的应用，同时在数学上与统计物理学建立了严格的联系。要研究的应用程序的具体示例包括新工具，用于界定马尔可夫链的混合时间和随机算法之间的代数连接与统计物理学中相变的经典理论之间的代数连接。

项目成果

The Non-Hardness of Approximating Circuit Size

近似电路尺寸的非困难性

• DOI: 10.1007/978-3-030-19955-5_2
• 发表时间: 2021
• 期刊: Theory of computing systems
• 影响因子: 0.5
• 作者: Allender, Eric;Ilango, Rahul;Vafa, Neekon
• 通讯作者: Vafa, Neekon

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

Ker-I Ko 与资源有限 Kolmogorov 复杂性研究

• DOI: 10.1007/978-3-030-41672-0_2
• 发表时间: 2020
• 期刊: Lecture notes in computer science
• 作者: Allender, Eric