Combinatorics and Probability Seminar
Title: The Complexity of Random Constraint Satisfaction Problems
Satisfiability problems appear to be hard even when generated randomly. To understand their complexity, we consider planted k-SAT/k-CSP where the clauses are drawn at random from those satisfying a fixed assignment. There are currently large gaps between the point at which the planted solution becomes unique (information-theoretically) and when it can be found efficiently (in time polynomial in the size of the input). For random k-SAT/k-CSP, the current best algorithms need roughly nk/2 clauses to find the planted assignment, although it becomes unique after roughly n log n clauses. Is this gap inherent? In this talk, we describe a “paring” transition as the number of clauses grows, and show how it directly affects the complexity of any statistical algorithm to detect planted solutions. Since known algorithmic techniques for these problems all have statistical counterparts, this is concrete evidence that planted k-SAT/k-CSP are intractable.
The talk is based on joint work with Vitaly Feldman and Will Perkins.
Combinatorics and Probability Seminar - S. Vempala, Georgia Tech
Thursday, March 10, 2016 - 4:00pm
12 Hillhouse AvenueNew Haven, CT 06511