{"560091":{"#nid":"560091","#data":{"type":"event","title":"ARC Colloquium: Rasmus Kyng (Yale)","body":[{"value":"\r\n\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/56087\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/56087\u003C\/a\u003E\u003C\/p\u003E\r\nFull collection of talk videos are available at:  \r\n\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\r\n\r\n\u003Cbr\u003E\r\n\u003Cbr\u003E\r\n\r\n\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\u003Ca href=\u0022http:\/\/cs.yale.edu\/homes\/rjkyng\/\u0022\u003E\u003Cstrong\u003ERasmus Kyng - Yale\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 28, 2016\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\u003Cstrong\u003ETitle: \u0026nbsp;\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003EApproximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/em\u003E\u003Cbr \/\u003E\r\nWe show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization \u0026ndash; the version of Gaussian elimination for positive semi-definite matrices. We compute this factorization by subsampling standard Gaussian elimination. This is the first nearly linear time solver for Laplacian systems that is based purely on random sampling, and does not use any graph theoretic constructions such as low-stretch trees, sparsifiers, or expanders. The crux of our proof is the use of matrix martingales to analyze the algorithm.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nRasmus Kyng is a PhD student in Computer Science at Yale University, advised by Dan Spielman. Before attending Yale, he received a BA in Computer Science from the University of Cambridge in 2011. His research interests include graph algorithms, applied and theoretical machine learning, and linear systems.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/www.cs.yale.edu\/homes\/rjkyng\/\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/www.cs.yale.edu\/homes\/rjkyng\/\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/arc.gatech.edu\/hg\/item\/564791\u0022\u003ESeminar webpage\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\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-08 10:36:54","changed_gmt":"2017-04-13 21:15:12","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-11-28T11:00:00-05:00","event_time_end":"2016-11-28T12:00:00-05:00","event_time_end_last":"2016-11-28T12:00:00-05:00","gmt_time_start":"2016-11-28 16:00:00","gmt_time_end":"2016-11-28 17:00:00","gmt_time_end_last":"2016-11-28 17: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"}],"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","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}