Lecture 1: ACO Student Seminar

Friday, March 1st, 1-2pm, Skiles 005

Title: Random Constraint Satisfaction Problems

Abstract:

A large variety of Constraint Satisfactoin Problems can be classified as "computationally hard". In recent years researchers from statistical mechanics have investigated such problems via non-rigorous methods. The aim of this talk is to give a brief overview of this work, and of the extent to which the physics ideas can be turned into rigorous mathematics. I'm also going to point out various open problems.

http://www.math.uni-frankfurt.de/~acoghlan/talk_AtlantaACO.pdf

Lecture 2: ARC Colloquium

Monday, March 4th, 1-2pm, Klaus 1116W

Title: Chasing the k-SAT Threshold"

Abstract:

Let F be a random Boolean formula in conjunctive normal form over n Boolean variables with m clauses of length k. The existence of a (non-uniform) sharp threshold for the satisfiability of such formulas is well known [Friedgut 1999]. However, despite considerable effort the precise location of this phase transition remains unknown for any k>2. The best previous upper and lower bounds differ by an additive $k\ln 2/2$ [Achlioptas, Peres 2003]. In this talk I present an improved lower bound, which reduces the gap to ~0.19. The proof is inspired by the cavity method of statistical mechanics.

http://www.math.uni-frankfurt.de/~acoghlan/talk_AtlantaSAT.pdf

Lecture 3:

Wednesday, March 6th, 11-12pm, Skiles 168

Title: Quiet Planting

Abstract:

One of the most important objects in the theory of random CSPs is the uniform distribution over the set of solutions of a given problem instance. For instance, computing the free entropy of this distribution would entail the precise location of the threshold for the existence of solutions. In this presentation I am going to present a way of accessing this distribution (under certain assumptions) via the so-called "planted model". I'm also going to show a few applications of this technique.

http://www.math.uni-frankfurt.de/~acoghlan/QuietPlanting.pdf