Computer Science/Discrete Mathematics Seminar II

Given a collection of constraints over a collection of variables consider the following generic constraint satisfaction algorithm: start with a random assignment of values to the variables; while violated constraints exist, select a random such constraint and address its violation by assigning fresh random values to its underlying variables. We will prove that this process terminates relatively quickly if the following is true: the amount of information (bits) needed to encode the newly violated constraints after each step is strictly less than the amount of randomness (bits) that will be consumed to address their violation later on. Based on joint work with Fotis Iliopoulos.