Extended Formulation Lower Bounds for Refuting Random CSPs

Jonah Brown-Cohen, Prasad Raghavendra

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…