The ACO Seminar (2012-2013)

The best current estimates of the thresholds for the existence of solutions in random constraint satisfaction problems mostly derive from the first and the second moment method. Yet apart from a very few exceptional cases these methods do not quite yield matching upper and lower bounds. Here we present an enhanced second moment argument that allows us to narrow the gap to an additive 2^{-(1-o_k(1))k} in the random k-NAESAT problem, one of the standard benchmarks in random CSPs. Based on joint work with Konstantinos Panagiotou and Lenka Zdeborova.