{"486601":{"#nid":"486601","#data":{"type":"event","title":"ARC Colloquium: John Wilmes - University of Chicago","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EJohn Wilmes \u2013 University of Chicago\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, January 25, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMiRC 102 A \u0026amp; B - 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EThe Isomorphism Problem for Highly Regular Structures\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe Graph Isomorphism (GI) problem has been notorious in computational complexity theory for its unresolved complexity status. Until Babai\u0027s recently announced quasipolynomial-time algorithm for GI, the worst-case time-complexity bound of $\\exp(\\tilde{O}(n^{1\/2}))$ where $n$ is the number of vertices (Babai--Luks, 1983), had stood for over 30 years.\u003C\/p\u003E\u003Cp\u003EAmong the obstacles Babai confronts in his recent breakthrough are primitive coherent configurations (PCCs), a class of highly-regular structures generalizing strongly regular graphs. In this talk, we will describe recent progress characterizing the structure and automorphism groups of PCCs and other highly-regular structures, with applications to GI, and we will describe the connections between these results and Babai\u0027s breakthrough.\u003C\/p\u003E\u003Cp\u003EIn particular, in joint work with Sun, we classify the PCCs with the most automorphisms. In joint work with Babai, Chen, Sun, and Teng, we give the first quasipolynomial-time algorithm for strongly regular GI over an entire interval of the exponent of the degree parameter. And in joint work with Babai, we give a $n^{O(\\log n)}$-time algorithm for the important special case of Steiner Design Isomorphism.\u0026nbsp; In all cases, our progress relies on new structural results we prove, especially on new bounds for the rate of expansion of small sets.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"MIRC 102 A \u0026 B at 1 pm"}],"uid":"27466","created_gmt":"2016-01-14 16:13:25","changed_gmt":"2017-04-13 21:17:07","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-01-25T12:00:00-05:00","event_time_end":"2016-01-25T13:00:00-05:00","event_time_end_last":"2016-01-25T13:00:00-05:00","gmt_time_start":"2016-01-25 17:00:00","gmt_time_end":"2016-01-25 18:00:00","gmt_time_end_last":"2016-01-25 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}