Speaker:

Amin Coja-Oghlan

Title:

Catching the k-NAESAT Threshold

Abstract:

The best current estimates of the thresholds for the existence of solutions in random CSPs 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 method 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 the theory or random CSPs. This is joint work with Konstantinos Panagiotou.