Combinatorics and Probability Seminar 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 n The talk is based on joint work with Vitaly Feldman and Will Perkins. |

# Combinatorics and Probability Seminar - S. Vempala, Georgia Tech

Event time:

Thursday, March 10, 2016 - 4:00pm

Location:

215 LOM

12 Hillhouse Avenue

New Haven, CT
06511
Event description: