ARC Colloquium: Amin Coja-Oghlan, Goethe University, Frankfurt, Germany

Title: Chasing the k-SAT threshold


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.

Event Details


  • Monday, March 4, 2013
    1:00 pm

For More Information Contact