DIMACS Working Group on Message-Passing Algorithms

October 13 - 17, 2008
DIMACS Center, CoRE Building, Rutgers University

Organizers:

Riccardo Zecchina, International Centre for Theoretical Physics (ICTP), riccardo.zecchina at polito.it

Gregory Sorkin, IBM Research, sorkin at watson.ibm.com

Workshop Program:

All talks except the survey / tutorial should be 30-45 minutes.
"Open session" time is for discussion around the talks or on other topics, or breaking into smaller groups.
The meeting will be informal, and it is expected that programme adjustments will occur as it progresses.


Monday, October 13, 2008

 9:30 - 10:15 Breakfast and registration

10:15 - 10:30 Welcome and opening remarks
              Tami Carpenter, DIMACS Associate Director

10:30 - 11:00 Algorithmic Phase Transitions in Constraint Satisfaction Problems
              Dimitris Achlioptas, UCSC 

11:00 - 11:30 Coffee break

11:30 - 12:30 The Walksat algorithm applied to random CNFs
              Amin Coja-Oghlan, University of Edinburgh 

              Open session
             
12:30 -  2:00 Lunch

 2:00 -  3:00 Andrea Montanari (survey / tutorial)

 3:00 -  3:30 Coffee break

 3:30 -  5:00 Discussion

 5:30 -  7:30 Dinner at DIMACS


Tuesday, October 14, 2008

 8:30 -  9:00 Breakfast and registration

 9:00 - 10:30 Misha Chertkov + Open session
              Inference with Fermions, Loops and Determinants 

10:30 - 11:00 Coffee break

11:00 - 12:30 Counting Independent Sets using BP for Sparse Graphs
              Jinwoo Shin, MIT
              
              Open session
             
12:30 -  2:00 Lunch

 2:00 -  3:30 Locked constraint satisfaction problems
              Lenka Zdeborova, Los Alamos National Laboratory 

              Open session
              
 3:30 -  4:00 Coffee break

 4:00 -  5:00 Discussion


Wednesday, October 15, 2008

 8:30 -  9:00 Breakfast and registration

 9:00 - 10:30 Long-range independence and combinatorial optimization with random costs
              David Gamarnik, MIT 

              Open session

10:30 - 11:00 Coffee break
 
11:00 - 12:30 Amir Dembo + Thierry Mora
              title TBA

12:30 -  2:00 Lunch

 2:00 -  5:00 Open session

 3:00 -  3:30 Coffee break

 3:30 -  5:00 Open session


Thursday, October 16, 2008

 8:30 -  9:00 Breakfast and registration

 9:00 - 11:00 Marc Mezard + open challenges discussion
              title TBA

11:00 - 11:30 Coffee break

11:30 - 12:30 Christian Borgs + Open session
              title TBA

12:30 -  2:00 Lunch

 2:00 -  3:00 Florent Krzakala + Open session
              Towards a Quantum Belief Propagation Algorithm

 3:00 -  3:30 Coffee break

 3:30 -  5:00 Open session


Friday, October 17, 2008

 8:30 -  9:00 Breakfast and registration

 9:00 - 10:30 Generating Random Graphs with Large Girth
              Mohsen Bayati, Microsoft Research 

              Open session
              
10:30 - 11:00 Coffee break

11:00 - 12:30 Open session

12:30 -  2:00 Lunch 

Previous: Participation

Workshop Index

DIMACS Homepage