{"601432":{"#nid":"601432","#data":{"type":"event","title":"ARC Colloquium:  Xiaorui Sun (Microsoft)","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\u003EXiaorui Sun\u0026nbsp;(Microsoft Research)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 12, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;\u0026nbsp; The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E \u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe study the edge query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n^{1+o(1)} queries, improving on the previous best bound of O~(n^{5\/4}). Since the problem is known to require \\Omega(n) queries, our algorithm is optimal up to a subpolynomial factor.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWhile trying to extend a known connection to distribution testing, discovered by Fischer and Matsliah (SICOMP 2008), one encounters a natural obstacle presented by sampling lower bounds such as the $\\Omega(n^{2\/3})$-sample lower bound for distribution closeness testing (Valiant, SICOMP 2011). In the context of graph isomorphism testing, these bounds lead to an $n^{1+\\Omega(1)}$ barrier for Fischer and Matsliah\u0026#39;s approach. We circumvent these limitations by exploiting a geometric representation of the connectivity of vertices. An approximate representation of similarities between vertices can be learned with a near-linear number of queries and allows relaxed versions of sampling and distribution testing problems to be solved more efficiently.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with Krzysztof Onak\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cs.columbia.edu\/~xiaoruisun\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":" The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds- Klaus 1116E at 11am"}],"uid":"32895","created_gmt":"2018-01-26 19:29:25","changed_gmt":"2018-02-16 21:10:52","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-03-12T12:00:00-04:00","event_time_end":"2018-03-12T13:00:00-04:00","event_time_end_last":"2018-03-12T13:00:00-04:00","gmt_time_start":"2018-03-12 16:00:00","gmt_time_end":"2018-03-12 17:00:00","gmt_time_end_last":"2018-03-12 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}