Tutte seminar - Jane Gao

Since the early 2000s statistical physicists have predicted, using a non-rigorous technique called the "cavity method", that the solution spaces of many random constraint satisfiability problems (CSPs) and combinatorial problems have a clustering phenomenon. When the density of a random CSP (the number of constraints divided by the number of variables) is below a critical value c^*, all solutions form a single well-connected cluster: one can "walk" from one solution to any other, via a path of solutions, by changing a small number of variables at a time. Above c^*, solutions are partitioned into exponentially many well-connected, well-separated clusters: the Hamming distance between any two solutions in different clusters is Ω(n). This clustering phenomenon was proved to be true for several random CSPs by mathematicians; it gives insight into the existence of an "algorithmic barrier" observed in many CSPs. In this talk, I will depict the clustering of random k-XORSAT solutions, in particular when the k-XORSAT density is approaching c^*, the clustering threshold: we investigate how clusters are born.
 

This is joint work with Mike Molloy.