Physics of Algorithms Workshop

Organizing committee: Michael Chertkov (LANL), Jason Johnson (LANL), Allon Percus (Claremont Graduate University), Lenka Zdeborova (LANL)

Optimization, inference and learning involve emerging computational problems in many areas of science and engineering. Typically stated in the framework of computer science and information theory, these problems are also linked to concepts and approaches native to statistical, mathematical and quantum physics.

This interdisciplinary field has seen a recent explosion of activity, resulting in new algorithms and new methods of analysis. Discrete computational challenges including constraint satisfaction and error correction have benefited from techniques and insights offered by statistical physics. Physics, at the same time, has been significantly enriched by approaches from discrete computation, such as convex optimization and message-passing algorithms.

Our conference will bring together leading experts from physics, computer science, machine learning, operation research and information theory to discuss the current hot topics and new challenges on the intersection of the fields. Specific topics will include:

• Graphical models
• Statistical Inference and Learning
• Monte Carlo Algorithms
• Belief Propagation and Message Passing Algorithms
• Satisfiability and Combinatorial Optimization
• Average-case Complexity
• Phase Transitions and Cavity Approach
• Combinatorial approaches relevant to walks, loops, closed subgraphs, etc.

Contact: Adam Shipman, conferences@cnls.lanl.gov.