Solution Clusters for Locked CSP's: Random XORSAT on a Fixed Degree Sequence

Wednesday, March 18, 2015 - 9:30am - 10:10am
Klaus 1116
Mike Molloy (University of Toronto)
Mezard and Zdeborova introduced the class of locked CSP's, which appear to be particularly challenging to solve. They considered Poisson degree sequences truncated so that the minimum degree is two. They discovered a threshold density: below that density all solutions belong to a single cluster; above that density every cluster contains O(1) solutions.

XORSAT is the locked problem that is most amenable to rigorous analysis. We provide a rigorous proof that, for XORSAT, the clusters are as described on a truncated Poisson degree sequence. We further show that on more general degree sequences, there can be an exponential number of clusters each with exponential size.

This is joint work with Lenka Zdeborova.