Strongly Refuting Random CSPs Below the Spectral Threshold

Prasad Raghavendra, Satish Rao, Tselil Schramm

Random constraint satisfaction problems (CSPs) are known to exhibit threshold phenomena: given a uniformly random instance of a CSP with $n$ variables and $m$ clauses, there is a v…