Reconstruction and Clustering in Random Constraint Satisfaction Problems

Andrea Montanari, Ricardo Restrepo, Prasad Tetali

Random instances of Constraint Satisfaction Problems (CSP's) appear to be hard for all known algorithms, when the number of constraints per variable lies in a certain interval. Con…