Random subcubes as a toy model for constraint satisfaction problems

Thierry Mora, Lenka Zdeborova

We present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the s…