Combinatorics and Probability Seminar - S. Vempala, Georgia Tech

Event time: 
Thursday, March 10, 2016 - 4:00pm
Location: 
215 LOM See map
12 Hillhouse Avenue
New Haven, CT 06511
Event description: 

Combinatorics and Probability Seminar
S. Vempala, Georgia Tech

Title: The Complexity of Random Constraint Satisfaction Problems

Abstract:

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.