{"446251":{"#nid":"446251","#data":{"type":"event","title":"ARC Colloquium: Anup Rao - Georgia Tech","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAnup Rao \u2013 Georgia Tech\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 26, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West \u2013 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\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe Stochastic Block Model and Communities in Sparse Random Graphs: Detection at Optimal Rate\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe consider the problem of communities detection in sparse random graphs. Our model is the so-called Stochastic Block Model, which has been immensely popular in the recent statistics literature. Let X1,...Xk be vertex sets of size n each (where k is fixed and n is large). One draws random edges inside each Xi with probability a\/n, and between Xi and Xj with probability b\/n, for some constants a and b. Given one instance of this sparse random graph, our goal is to recover the sets Xi as correctly as possible. We are going to present a fast spectral algorithm which does this job at the optimal rate (namely the relation between a,b and the number of mistakes in the recovery is optimal). Our algorithm is based on spectral properties of random sparse matrices and is easy to implement. We will also discuss some related works with spectral algorithms and an open question concerning random matrices.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-10 09:44:12","changed_gmt":"2017-04-13 21:18:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-10-26T14:00:00-04:00","event_time_end":"2015-10-26T15:00:00-04:00","event_time_end_last":"2015-10-26T15:00:00-04:00","gmt_time_start":"2015-10-26 18:00:00","gmt_time_end":"2015-10-26 19:00:00","gmt_time_end_last":"2015-10-26 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"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":""}}}