Skip Navigation Links

Project Information

AF: SMALL: INFORMATION COMPRESSION ARGUMENTS

Agency:
NSF

National Science Foundation

Project Number:
1422102
Contact PI / Project Leader:
SZEGEDY, MARIO
Awardee Organization:
RUTGERS THE ST UNIV OF NJ NEW BRUNSWICK

Description

Abstract Text:
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.
Project Terms:
Accidents; Algorithms; computer science; Development; Generations; graduate student; Hand; High temperature of physical object; interest; Modeling; Nature; Phase Transition; Physics; Randomized; Research; Side; Solutions; theories; undergraduate student; Universities; Yang

Details

Contact PI / Project Leader Information:
Name:  SZEGEDY, MARIO
Other PI Information:
Not Applicable
Awardee Organization:
Name:  RUTGERS THE ST UNIV OF NJ NEW BRUNSWICK
City:  NEW BRUNSWICK    
Country:  UNITED STATES
Congressional District:
State Code:  NJ
District:  06
Other Information:
Fiscal Year: 2014
Award Notice Date: 06-Aug-2014
DUNS Number: 001912864
Project Start Date: 01-Sep-2014
Budget Start Date:
CFDA Code: 47.070
Project End Date: 31-Aug-2015
Budget End Date:
Agency: ?

Agency: The entity responsible for the administering of a research grant, project, or contract. This may represent a federal department, agency, or sub-agency (institute or center). Details on agencies in Federal RePORTER can be found in the FAQ page.

National Science Foundation
Project Funding Information for 2014:
Year Agency

Agency: The entity responsible for the administering of a research grant, project, or contract. This may represent a federal department, agency, or sub-agency (institute or center). Details on agencies in Federal RePORTER can be found in the FAQ page.

FY Total Cost
2014 NSF

National Science Foundation

$154,214

Results

i

It is important to recognize, and consider in any interpretation of Federal RePORTER data, that the publication and patent information cannot be associated with any particular year of a research project. The lag between research being conducted and the availability of its results in a publication or patent award varies substantially. For that reason, it's difficult, if not impossible, to associate a publication or patent with any specific year of the project. Likewise, it is not possible to associate a publication or patent with any particular supplement to a research project or a particular subproject of a multi-project grant.

ABOUT FEDERAL REPORTER RESULTS

Publications: i

Click on the column header to sort the results

PubMed = PubMed PubMed Central = PubMed Central Google Scholar = Google Scholar

Patents: i

Click on the column header to sort the results

Similar Projects

Download Adobe Acrobat Reader:Adobe Acrobat VERSION: 3.41.0 Release Notes
Back to Top