Solving Random Planted CSPs

Abstract: A constraint satisfaction problem (CSP) is a computational problem with n boolean variables together with a collection of logical constraints, each depending on only a few of the variables. The goal is to find an assignment of true/false values that satisfies as many constraints as possible. One example of a CSP is the k-SAT problem, in which each constraint contains k variables and is satisfied when at least one of them is true. While solving CSPs is computationally hard in general, requiring exponential time unless the number of constraints is very large, random planted CSPs, where we first choose an assignment and then generate random constraints that it satisfies, are more tractable. We present an algorithm to solve random CSPs with n*polylog(n) constraints in subexponential time.