{"661207":{"#nid":"661207","#data":{"type":"event","title":"ARC Colloquium: Elizabeth Yang (Berkeley)","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\u003EElizabeth Yang (Berkeley)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EJanuary 23, 2023\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EPettit Microelectronics Building 102 A\u0026amp;B - 3:30 pm\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Testing thresholds for high-dimensional random geometric graphs\u003Cstrong\u003E \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp;\u0026nbsp;\u003C\/strong\u003EIn the random geometric graph model, we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere, and we connect pairs of vertices whose vectors are \u0026quot;sufficiently close,\u0026quot; such that the marginal probability of each edge is p.\u0026nbsp;We investigate the problem of distinguishing an Erd\u0151s-R\u0026eacute;nyi graph from a random geometric graph.\u0026nbsp;When p = c \/ n for constant c, we prove that if d \u0026ge; poly log n, the total variation distance between the two distributions is close to 0; this improves upon the best previous bound of Brennan, Bresler, and Nagaraj (2020), which required d \u0026gt;\u0026gt; n^{3\/2}. Furthermore, our result is nearly tight, resolving a conjecture of Bubeck, Ding, Eldan, \u0026amp; R\u0026aacute;cz (2016) up to logarithmic factors.\u0026nbsp;We also obtain improved upper bounds on the statistical indistinguishability thresholds in d for the full range of p satisfying 1\/n \u0026le; p \u0026le; 1\/2, improving upon the previous bounds by polynomial factors.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, we will discuss the key ideas in our proof, which include:\u003Cbr \/\u003E\r\n- Sharp estimates for the area of the intersection of a random sphere cap with an arbitrary subset of the sphere, which are obtained using optimal transport maps and entropy-transport inequalities on the unit sphere.\u003Cbr \/\u003E\r\n- Analyzing the Belief Propagation algorithm to characterize the distributions of (subsets of) the random vectors conditioned on producing a particular graph.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nBased on joint work with Siqi Liu, Sidhanth Mohanty, and Tselil Schramm.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/people.eecs.berkeley.edu\/~elizabeth_yang\/\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\u003Cem\u003E and \u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E \u003C\/em\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@Klauscc.gatech.edu\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Testing thresholds for high-dimensional random geometric graphs - Pettit Microelectronics Building 102 A\u0026B at 3:30pm"}],"uid":"35702","created_gmt":"2022-09-15 14:49:25","changed_gmt":"2023-01-12 20:48:26","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-01-23T15:30:00-05:00","event_time_end":"2023-01-23T16:30:00-05:00","event_time_end_last":"2023-01-23T16:30:00-05:00","gmt_time_start":"2023-01-23 20:30:00","gmt_time_end":"2023-01-23 21:30:00","gmt_time_end_last":"2023-01-23 21:30: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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}