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

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

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.