"Solving Large-Scale Computational Problems Using Insights from Statistical Physics", Professor Bart Selman, Cornell University
Many challenging problems in computer science and related fields can be formu- lated as constraint satisfaction problems. Such problems consist of a set of discrete variables and a set of constraints between those variables, and represent a general class of so-called NP-complete problems. The goal is to find a value assignment to the variables that satisfies all constraints, generally requiring a search through and exponentially large space of variable-value assignments. Models for disordered systems, as studied in statistical physics, can provide important new insights into the nature of constraint satisfaction problems. Recently, work in this area has resulted in the discovery of a new method for solving such problems, called the survey propagation (SP) method. With SP, we can solve problems with millions of variables and constraints, an improvement of two orders of magnitude over previous methods.
The Princeton Plasma Physics Laboratory 2012-2013 Colloquium Committee is comprised of the following people. Please feel free to contact them by e-mail regarding any possible speakers or topics for future colloquia.