AF: Small: Information Compression Arguments

AF：小：信息压缩参数

• 批准号: 1422102
• 负责人: Mario Szegedy
• 金额: $ 15.42万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2018-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1422102&HistoricalAwards=false
• 关键词: AF; Small; Information; Compression; Arguments

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.

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