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

Friday, May 22, 2015 - 10:20am - 11:10am
Keller 3-180
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 may be an exponential number of clusters each with exponential size. We also discuss the connection with small noise reconstruction.

This is joint work with Lenka Zdeborova.
MSC Code: