Extended formulation lower bounds for refuting random CSPs

Random constraint satisfaction problems (CSPs) such as random 3-SAT are conjectured to be computationally intractable. The average case hardness of random 3-SAT and other CSPs has broad and far-reaching implications on problems in approximation, learning theory and cryptography.