RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

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

November 30, 2016 - 11:00am
Mario Szegedy
Rutgers University

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.

CSS 3100A

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to