Solution geometry of a random k-XORSAT near the clustering threshold
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 5158|
Since early 2000s statistical physicists 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 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 O(log n) 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). These clustering phenomena were proved to be true for several random CSPs by mathematicians. In this talk, I will depict clustering of random k-XORSAT solutions, in particular when its density is approaching c*, the clustering threshold: we investigate how clusters are born.
This is joint work with Mike Molloy.
200 University Avenue West
Waterloo, ON N2L 3G1