{"199631":{"#nid":"199631","#data":{"type":"profile","title":"Amin Coja-Oghlan - Profile","body":[{"value":"\u003Cp\u003EAmin conducted three lectures during March 1 \u2013 8, 2013\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELecture 1: ACO Student Seminar\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFriday, March 1st, 1-2pm, Skiles 005\u003C\/p\u003E\u003Cp\u003ETitle: Random Constraint Satisfaction Problems\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EA large variety of Constraint Satisfactoin Problems can be classified as \u0022computationally hard\u0022. 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\u0027m also going to point out various open problems.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.math.uni-frankfurt.de\/~acoghlan\/talk_AtlantaACO.pdf\u0022\u003Ehttp:\/\/www.math.uni-frankfurt.de\/~acoghlan\/talk_AtlantaACO.pdf\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELecture 2: ARC Colloquium\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMonday, March 4th, 1-2pm, Klaus 1116W\u003C\/p\u003E\u003Cp\u003ETitle: Chasing the k-SAT Threshold\u0022\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003ELet 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\u0026gt;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.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.math.uni-frankfurt.de\/~acoghlan\/talk_AtlantaSAT.pdf\u0022\u003Ehttp:\/\/www.math.uni-frankfurt.de\/~acoghlan\/talk_AtlantaSAT.pdf\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELecture 3:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWednesday, March 6th, 11-12pm, Skiles 168\u003C\/p\u003E\u003Cp\u003ETitle: Quiet Planting\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EOne 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 \u0022planted model\u0022. I\u0027m also going to show a few applications of this technique.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.math.uni-frankfurt.de\/~acoghlan\/QuietPlanting.pdf\u0022\u003Ehttp:\/\/www.math.uni-frankfurt.de\/~acoghlan\/QuietPlanting.pdf\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-03-15 08:59:40","changed_gmt":"2013-07-26 17:16:53","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","extras":[],"hg_media":{"199601":{"id":"199601","type":"image","title":"Amin Coja-Oghlan","body":null,"created":"1449179934","gmt_created":"2015-12-03 21:58:54","changed":"1475894853","gmt_changed":"2016-10-08 02:47:33","alt":"Amin Coja-Oghlan","file":{"fid":"196529","name":"amin.jpg","image_path":"\/sites\/default\/files\/images\/amin_1.jpg","image_full_path":"http:\/\/tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/amin_1.jpg","mime":"image\/jpeg","size":8438,"path_740":"http:\/\/tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/amin_1.jpg?itok=Ava4QOcf"}}},"media_ids":["199601"],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[{"id":"61551","name":"Goethe University Frankfurt\/Main"}],"classification":["Guest speaker"],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}