{"560111":{"#nid":"560111","#data":{"type":"event","title":"ARC Colloquium: Ramamohan Paturi (UCSD)","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\u003ERamamohan Paturi (UCSD)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 13, 2017\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 \u003Cem\u003EGenesis of ETH and SETH\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nSeveral researchers have found ETH (Exponential Time Hypothesis) and Strong ETH to be useful and proved matching lower bounds for several problems in P as well as NP  based on these conjectures. In this talk, I will talk about the technical results that motivated these conjectures. Specifically, I will talk about the following results:\r\n\u003Cul\u003E\u003Cli\u003Eif ETH is false then a number of other NP-complete problems (the class SNP)  will also have subexponential time algorithms, and \r\nthe complexity of k-SAT must keep increasing with k under ETH. \r\n\u003C\/ul\u003E\r\nWhile these results are old, the latter result  is relatively less well-known and I hope that it might inspire more work along the lines.\r\n\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E-----------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESpeaker\u0026#39;s webpage: \u003Ca href=\u0022http:\/\/jacobsschool.ucsd.edu\/faculty\/faculty_bios\/index.sfe?fmp_recid=118\u0022\u003Ehttp:\/\/jacobsschool.ucsd.edu\/faculty\/faculty_bios\/index.sfe?fmp_recid=118\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EVideos of recent talks are available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022 target=\u0022_BLANK\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022 target=\u0022_BLANK\u0022\u003EClick here to subscribe to the ARC Colloquium mailing list.\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Genesis of ETH and SETH (Klaus 1116 E at 11 am)"}],"uid":"27466","created_gmt":"2016-08-08 10:46:50","changed_gmt":"2017-04-13 21:15:12","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-02-13T11:00:00-05:00","event_time_end":"2017-02-13T12:00:00-05:00","event_time_end_last":"2017-02-13T12:00:00-05:00","gmt_time_start":"2017-02-13 16:00:00","gmt_time_end":"2017-02-13 17:00:00","gmt_time_end_last":"2017-02-13 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq","title":"Click here to subscribe to the seminar email list."}],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm 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":"Eric Vigoda","format":"plain_text"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}