BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Strongly refuting random constraint satisfaction problems below the spectral threshold Schramm, Tselil


Random CSPs are known to be unsatisfiable with high probability when the number of clauses is at least linear. However, the task of refuting random CSPs is hypothesized to be computationally hard if there are O(N) clauses--in fact, the best known efficient algorithms for the strong refutation of most k-CSPs require instances with at least \Omega(N^{k/2}) clauses, a polynomial factor beyond the unsatisfiability threshold at \Theta(N). In this talk, I will describe a new spectral algorithm that strongly refutes random CSPs with fewer clauses, given more time. Our algorithm interpolates between the efficient algorithms at the spectral threshold and brute-force search at the unsatisfiability threshold. This result also implies tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere. Based on joint work with Prasad Raghavendra and Satish Rao.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International