Show simple item record

dc.contributor.authorSun, Xiaorui
dc.date.accessioned2018-03-21T19:15:13Z
dc.date.available2018-03-21T19:15:13Z
dc.date.issued2018-03-12
dc.identifier.urihttp://hdl.handle.net/1853/59432
dc.descriptionPresented on March 12, 2018 at 11:00 a.m. in the Klaus Advanced Computing Building, Room 1116E.en_US
dc.descriptionXiaorui Sun is a postdoctoral researcher at Microsoft Research Redmond. Prior to joining Microsoft, he was a Google Research Fellow at Simons Institute at UC Berkeley. His research focuses on the design and analysis of algorithms with an emphasis on big data processing, including algorithmic graph theory, massively parallel computing and machine learning theory.en_US
dc.descriptionRuntime: 58:39 minutesen_US
dc.description.abstractWe 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. While 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'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. Joint work with Krzysztof Onaken_US
dc.format.extent58:39 minutes
dc.language.isoen_USen_US
dc.relation.ispartofseriesARC Colloquiumen_US
dc.subjectGraph isomorphismen_US
dc.titleThe Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Boundsen_US
dc.typeLectureen_US
dc.typeVideoen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameMicrosoft Researchen_US


Files in this item

This item appears in the following Collection(s)

  • ARC Talks and Events [84]
    Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community

Show simple item record