Tractability as compressibility

Computer Science/Discrete Mathematics Seminar II
Topic:Tractability as compressibility
Speaker:Dimitris Achlioptas
Affiliation:University of California, Santa Cruz
Date:Tuesday, March 24
Time/Room:10:30am - 12:30pm/S-101

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.