Abstract
We consider random (or sufficiently pseudorandom) instances of a constraint satisfaction problem with n variables, m = m(n) constraints, and constraint predicate F. Given a certain running time n^r for the "SOS algorithm", how strong an upper-bound 1-delta can be placed on the maximum fraction of simultaneously satisfiable constraints?
We establish the optimal 3-way tradeoff between m, r, and delta, in terms of F, generalizing all previously known lower bounds in the area.
Perhaps the most interesting contribution is a new and improved definition for the "closure" of a set of constraints in a CSP, a graph-theoretic concept heavily used in previous work on proof complexity.
joint work with Pravesh Kothari, Ryuhei Mori, and David Witmer