What does the Moser-Tardos RESAMPLE algorithm do when it does not work?

QuICS Seminar

Speaker: 
Mario Szegedy (Rutgers University)
Time: 
Wednesday, November 30, 2016 - 11:00am
Location: 
CSS 3100A
The celebrated Lovasz Local Lemma (LLL) guarantees that locally sparse systems always have solutions, which one can also algorithmically find by the Moser-Tardos RESAMPLE algorithm. Among the major questions that remain open is  that  how far *beyond* Lovasz's condition can we expect that RESAMPLE still performs in polynomial (linear) expected running time? Stating the question correctly is a challenge already. For a solvable and fixed instance RESAMPLE always comes up with a solution, but the catch is that the number of steps may be very large. We have therefore looked at parameterized instance families and tried to identify phase transitions in terms of these parameters. Perhaps the biggest lesson we have learned is that if we want to see phase transition thresholds, i.e. identify parameter values where RESAMPLE ``stops working,'' we need to understand what happens when RESAMPLE does *not* work. We have noticed that in this case the algorithm settles at a metastable equilibrium (at least for the homogenous instances we have considered), a phenomenon mostly studied for physical systems. We demonstrate (and illustrate) many of the interesting findings on a simple Coin Chain (spin chain) model. Even for this simple model some major mysteries are remaining.