{"663676":{"#nid":"663676","#data":{"type":"event","title":"ARC Colloquium: Guy Bresler (MIT) ","body":[{"value":"\u003Ch3\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003EGuy Bresler (MIT)\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003EMarch 13, 2023\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003EKlaus 1116 - 11:00 am\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Ch3\u003E\u0026nbsp;\u003C\/h3\u003E\r\n\r\n\u003Ch3\u003E\u0026nbsp;\u003C\/h3\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003ETitle:\u0026nbsp;Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract: There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. As a concrete instance of a more general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). In order to analyze our reduction we develop new methods for bounding the total variation distance between dependent distributions.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio\u003C\/strong\u003E:\u0026nbsp;Guy\u0026nbsp;Bresler\u0026nbsp;is an associate professor in the Department of Electrical Engineering and Computer Science at MIT, and a member of LIDS and IDSS. A major focus of his research is on the computational complexity of statistical inference, a direction that combines his interests in information theory, probability, and computation. \u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.mit.edu\/~gbresler\/\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":"Title    Title: Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: Klaus 1116 at 11:00 AM"}],"uid":"35702","created_gmt":"2022-12-06 23:33:28","changed_gmt":"2023-03-06 23:17:13","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2023-03-13T12:00:00-04:00","event_time_end":"2023-03-13T13:00:00-04:00","event_time_end_last":"2023-03-13T13:00:00-04:00","gmt_time_start":"2023-03-13 16:00:00","gmt_time_end":"2023-03-13 17:00:00","gmt_time_end_last":"2023-03-13 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":"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":""}}}