Bio
Amin conducted three lectures during March 1 – 8, 2013
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
