Home

Registration

Invited Speakers

Program

Abstracts

Local Information

Program

The workshop will be held in the Chaco Ballroom of The Inn at Loretto. We have scheduled 35+5 minutes for long talks and 15+5 minutes for short talks (5 minutes being reserved for questions/discussion). We will hold a half-day schedule on Friday.

Sunday, August 30

• 9:00-10:00pm. Early registration, Inn at Loretto lobby.

Monday, August 31

• 8:00-8:45. Registration & Informal Discussions (breakfast provided).

Morning Session, Chair: Michael Chertkov

• 8:45-9:00. Welcome/Opening Remarks: Alan Bishop, Associate Director of LANL for Theory, Simulation, and Computation. slides (pdf)

• 9:00-9:40. Jonathan Yedidia, Divide & Concur and Difference-Map Belief Propagation.
• 9:40-10:20. Martin Wainwright, On the sample complexity of graphical model selection: Practical methods and fundamental limits.
• 10:20- 10:35. Coffee Break.
• 10:35- 11:15. Amir Globerson, Finding k-best solutions using LP relaxations.
• 11:15- 11:55. Shiro Ikeda, Mean field approximation methods and information geometry.
• 11:55- 12:15. David Sontag, Approximate Inference in Graphical Models using LP Relaxations.

• 12:15- 2:00. Lunch Break.

Afternoon Session, Chair: Lenka Zdeborova

• 2:00-2:40. Susan Coppersmith, Quantum random walks of interacting particles and the graph isomorphism problem.
• 2:40-3:20. Jon Machta, Physics and phase transitions in parallel computational complexity.
• 3:20-3:40. Raghunandan Keshavan, Matrix completion from a Few Entries.
• 3:40-3:55. Coffee Break.
• 3:55-4:35. Stefan Boettcher, Extremal Optimization: Dynamics and Results.
• 4:35-5:15. Alan Middleton, Exact Sampling and Optimization Applied to Glassy Models.
• 5:15-5:35. Eli Ben-Naim, Traveling fronts in the simplex algorithm.

Tuesday, September 1

• 8:00-9:00. Registration & Informal Discussions (breakfast provided)

Morning Session, Chair: Florent Krzakala

• 9:00-9:40. Devavrat Shah, Inferring Rankings Under Constrained Sensing.
• 9:40-10:20. David Gamarnik, Combinatorial approach to Guerra's interpolation method.
• 10:20-10:35. Coffee Break.
• 10:35-11:15. Michael Chertkov (standing in for Vladimir Chernyak), Planar and Surface Graphical Models which are Easy.
• 11:15-11:55. Mohsen Bayati, Algorithms for Large, Sparse Network Alignment Problems.
• 11:55-12:15. Vincenc Gomez, Approximate inference on planar graphs using Loop Calculus and Belief Propagation

• 11:55-2:00. Lunch Break.

Afternoon Session, Chair: Eli Ben-Naim

• 2:00-2:40. Alistair Sinclair, The Solid-on-Solid Model: A Case Study in Mixing Times.
• 2:40-3:20. Martin Loebl, Optimization by Enumeration.
• 3:20-3:40. Jinwoo Shin, Counting Independent Sets Using the Bethe Approximation .
• 3:40-3:55. Coffee Break.
• 3:55-4:35. Johan Wastlund, Replica Symmetry and Combinatorial Optimization.
• 4:35-5:15. Thomas Hayes, Graph Spectra, Rapid Mixing and Dobrushin's Uniqueness.

• 5:15-6:15. Discussion Topic: What is "Physics of Algorithms"? Opening comments/provocations by Werner Krauth, Cris Moore and Alistair Sinclair (~5 minutes each).

Wednesday, September 2

• 8:00-9:00. Registration & Informal Discussions (breakfast provided).

Morning Session, Chair: Pieter Swart

• 9:00-9:40. Ruediger Urbanke, Polar Codes---A New Paradigm for Coding.
• 9:40-10:20. David Donoho, Message Passing Algorithms for Compressed Sensing.
• 10:20-10:35. Coffee Break.
• 10:35-11:15. Neri Merhav, Statistical Physics of Information Measures.
• 11:15-11:55. Pascal Vontobel, A Graph-Dynamics Interpretation of the Sum-Product Algorithm.
• 11:55-12:15. Shashi Chillapagari, Algorithmic and Combinatorial Methods to Discover Low Weight Pseudo-Codewords.

• 12:15-2:00. Lunch Break.

Afternoon Session, Chair: Allon Percus

• 2:00-2:40. Cris Moore, Phase transitions in quantum satisfiability.
• 2:40-3:20. Federico Ricci-Tersenghi, Replica cluster variational method for spin glasses.
• 3:20-3:40. Theophane Weber, Average-case complexity of Maximum Weight Independent Set with random weights in bounded degree graphs.
• 3:40-3:55. Coffee Break.
• 3:55-4:35. Lenka Zdeborova, New results on glassy aspect of random optimization problems.
• 4:35-5:15. Florent Krzakala, Generating solutions of "impossible-to-solve" problems and simulating "impossible-to-simulate" models.
• 5:15-5:55. Rick Chartrand, Fast algorithms for nonconvex compressive sensing.

• 7:00. Evening Banquet Session (dinner provided), Banquet Speaker: Robert Ecke, Director of Center for Nonlinear Studies, LANL.

Thurdsay, September 3

• 8:00-9:00. Registration & Informal Discussions (breakfast provided).

Morning Session, Chair: Nick Hengartner

• 9:00-9:40. Bart Selman, Probabilistic and Logical Inference Methods for Model Counting and Sampling.
• 9:40-10:20. Sekhar Tatikonda, Message-Passing Algorithms in the Non-unique Gibbs Measure Regime.
• 10:20-10:35. Coffee Break.
• 10:35-11:15. Allon Percus, The Peculiar Phase Structure of Random Graph Bisection .
• 11:15-11:55. Jason Johnson, Orbit-Product Representation and Correction of Gaussian Belief Propagation.
• 11:55-12:15. Dmitry Malioutov, Sequential Compressed Sensing.

• 12:15-2:00. Lunch Break.

Afternoon Session, Chair: Jason Johnson

• 2:00-2:40. Werner Krauth, Classical and quantum hard spheres: from cluster algorithms to event-chains, from 2d melting to quasi-two dimensional quantum gases.
• 2:40-3:20. Konstantin Turitsyn, Breaking reversibility to accelerate Markov Chain Monte Carlo algorithms.
• 3:20-3:40. Lukas Kroc, Counting Solution Clusters Using Belief Propagation.
• 3:40-3:55. Coffee Break.
• 3:55-4:35. Koji Hukushima, An extended ensemble Monte Carlo study for ideal glass transition.
• 4:35-5:15. Heiko Rieger, Geometry of domain walls in disordered 2d systems.

• 5:15-6:15. Discussion Topic: Does Belief Propagation live up to its reputation? (or "BP or not BP") Opening comments/provocations by Jonathan Yedidia, Devavrat Shah and Federico Ricci Tersenghi (~5 minutes each).

Friday, September 4

• 8:00-9:00. Registration & Informal Discussions (breakfast provided).

Morning Session, Chair: Aric Hagberg

• 9:00-9:40. Alex Dimakis, Mixing times and Gossip algorithms.
• 9:40-10:00. Yusuke Watanabe, Graph zeta function in the Bethe free energy.
• 10:00-10:20. Tobias Galla, Intrinsic noise in game dynamical learning.
• 10:20-10:40. Coffee Break.
• 10:40-11:00. Dmitry Keselman, Resource Allocation under the Contingency Planning.
• 11:00-11:40. Leonid Gurvits, Convex relaxations of mixed derivatives of multivariate entire functions/polynomials.
• 11:40-11:45. Good bye word.

• 1:00. Grand Canyon teams depart (let us know if you want to join).

Saturday, September 5

Grand Canyon trips (North-South, South-North = 2 teams...and anything in between)

Sunday, September 6

Reunion of the two teams at Page & Lake Powell relaxation for survivors.