{"582448":{"#nid":"582448","#data":{"type":"event","title":"ARC Colloquium: David Witmer - CMU","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EDavid Witmer - CMU\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, December 5, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nUsing the sum of squares hierarchy to refute random CSPs\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nConsider a random constraint satisfaction problem (CSP) over $n$ variables with $m = \u0026Delta; n$ constraints, each being a predicate $P$ applied to $k$ random literals. When \u0026Delta; \u003E\u003E 1$, the instance will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation --- i.e., a certificate of unsatisfiability.\u0026nbsp; Understanding the density required for average-case refutation is important in various areas of complexity including cryptography, proof complexity, and learning theory.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, we discuss refutation of random CSPs using the sum of squares (SOS) hierarchy.\u0026nbsp; The SOS hierarchy is a sequence of semidefinite relaxations parameterized by a value called the degree.\u0026nbsp; As the degree increases, the relaxation becomes tighter, but the size of its description increases.\u0026nbsp; We give an overview of recent work proving that the SOS degree required to refute a random instance of CSP$(P)$ is essentially determined by the smallest $t$ for which $P$ does not support a $t$-wise uniform distribution over satisfying assignments.\u0026nbsp; Specifically, if $P$ fails to support a $t$-wise uniform distribution, our work together with recent work of Raghavendra, Rao, and Schramm shows that degree-$\\frac{n}{\\Delta^{2\/(t-2)}}$ SOS can refute random instances of CSP$(P)$.\u0026nbsp; Furthermore, this result is tight up to polylogarithmic factors.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk is based on joint work with Sarah R. Allen, Pravesh Kothari, Ryuhei Mori, and Ryan O\u0026rsquo;Donnell.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/www.cs.cmu.edu\/~dwitmer\/\u0022\u003Ehttp:\/\/www.cs.cmu.edu\/~dwitmer\/\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESeminar webpage: \u003Ca href=\u0022http:\/\/arc.gatech.edu\/hg\/item\/582448\u0022\u003Ehttp:\/\/arc.gatech.edu\/hg\/item\/582448\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/114\u0022\u003EFall 2016 ARC Seminar Schedule\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Using the sum of squares hierarchy to refute random CSPs (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-10-12 17:27:11","changed_gmt":"2017-04-13 21:14:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-12-05T11:00:00-05:00","event_time_end":"2016-12-05T12:00:00-05:00","event_time_end_last":"2016-12-05T12:00:00-05:00","gmt_time_start":"2016-12-05 16:00:00","gmt_time_end":"2016-12-05 17:00:00","gmt_time_end_last":"2016-12-05 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"id":"50877","name":"School of Computational Science and Engineering"}],"categories":[],"keywords":[{"id":"92341","name":"Algorithms and Randomness Center"},{"id":"4265","name":"ARC"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003C\/p\u003E\r\n\r\n\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}