Videos

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

Presenter
May 22, 2015
Keywords:
  • Sequences
MSC:
  • 97I30
Abstract
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.