AF: Small: Information Compression Arguments

在这个为期一年的项目中，PI将专注于局部随机化算法与Lovasz局部引理(LLL)和物理学等相关界限之间的密切联系。自2003年以来，微光效应的分析与反铁磁伊辛模型的分析有着密切的联系。在一个令人兴奋的最新发展中，PI可以确定同时包含铁磁和反铁磁相互作用的伊辛模型的相变值。因此，人们期待着著名的Lee-Yang圆定理的推广，也许更令人兴奋的是，在计算机科学方面，一种新的微积分。PI进一步结合了物理学和计算机科学，计划解决主要问题，如生成令人满意的随机作业，以及找到满足给定大部分约束的作业。在PI计划研究的各种算法中，最有趣的是高温版本的Moser-Tardos重采样(MT)算法。拟议的研究将通过解决可满足性问题和使用受物理启发的算法生成随机解来影响计算机科学。该项目的最大挑战之一是确定保证解决方案存在的问题参数。越来越多的证据表明，最优参数符合统计场论中的某些阈值。PI认为这不是偶然的，找出物理和计算机科学问题之间联系的确切本质将具有巨大的智力价值。一方面，计算机科学提供了有趣的信息瓶颈方法，而另一方面，物理学家通过配分函数的零点来研究阈值。通过将这两个领域的不同方法结合在一起，PI计划为这两个领域注入全新的想法。该项目将为罗格斯大学一名有才华的研究生和一到两名本科生提供研究机会。

In this one-year project the PI will concentrate on the close connection beween local randomized algorithms and associated bounds like the Lovasz Local Lemma (LLL) and physics. It has been known since 2003 that the analysis of LLL and that of the anti-ferromagnetic Ising model are intimately related. In an exciting very recent development the PI could determine phase transition values for Ising models that contain both ferromagnetic and anti-ferromagnetic interactions. As a result, an extension of the well-known Lee-Yang circle theorem is expected, and maybe more excitingly, on the computer science side a new kind of LLL. Combining physics and computer science even further, the PI plans to tackle major problems such as generation of random satisfying assignments and finding assignments that satisfy a given large fraction of constraints. Among the variety of algorithms the PI plans to look at, the most interesting ones are ``high temperature'' versions of the Moser-Tardos resample (MT) algorithm.The proposed research will impact computer science via solving satisfiability problems and generating random solutions with physics-inspired algorithms. One of the great challenges of the project is to determine the problem parameters that guarantee the existence of the solutions. There is mounting evidence that the optimal parameters coincide with certain threshold values in statistical field theory. The PI believes that this is not an accident, and finding out the exact nature of the connection between the physics and computer science problems would have great intellectual merits. On one hand computer science offers interesting information-bottleneck approaches, while on the other hand physicists study the thresholds through zeroes of partition functions. By pulling together different approaches from the two fields, the PI plans to inject radically new ideas into both. The project will offer research opportunities for a talented graduate student and for one or two undergraduate students at Rutgers University.