7 citations · 7 across the 2 of their papers we have counts for
2 papers
cs.DM2012
Frozen variables in random boolean constraint satisfaction problems
Michael Molloy, Ricardo Restrepo
We determine the exact freezing threshold, r^f, for a family of models of random boolean constraint satisfaction problems, including NAE-SAT and hypergraph 2-colouring, when the co…
cs.DM2009★ 7 cited
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…