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.