Computer Science/Discrete Mathematics Seminar II

Tractability as compressibility

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.

Date & Time

March 24, 2015 | 10:30am – 12:30pm

Location

S-101

Speakers

Dimitris Achlioptas

Affiliation

University of California, Santa Cruz