{"440601":{"#nid":"440601","#data":{"type":"event","title":"SIAM Conference on Discrete Mathematics","body":[{"value":"\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.siam.org\/meetings\/dm16\/index.php\u0022 title=\u0022http:\/\/www.siam.org\/meetings\/dm16\/index.php\u0022\u003Ehttp:\/\/www.siam.org\/meetings\/dm16\/index.php\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EOrganizing Committee Co-Chairs\u003C\/strong\u003E\u003Cbr \/\u003E Henry Cohn, Microsoft Research New England, USA\u003Cbr \/\u003E Dana Randall, Georgia Institute of Technology, USA\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Georgia State University: http:\/\/www.siam.org\/meetings\/dm16\/index.php"}],"uid":"27466","created_gmt":"2015-08-26 11:39:38","changed_gmt":"2017-04-13 21:18:32","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-06-06T09:00:00-04:00","event_time_end":"2016-06-10T18:00:00-04:00","event_time_end_last":"2016-06-10T18:00:00-04:00","gmt_time_start":"2016-06-06 13:00:00","gmt_time_end":"2016-06-10 22:00:00","gmt_time_end_last":"2016-06-10 22:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.siam.org\/meetings\/dm16\/index.php","title":"SIAM Conference on Discrete Mathematics"}],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"10467","name":"Dana Randall"},{"id":"10176","name":"discrete mathematics"},{"id":"168079","name":"SIAM Conference"}],"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":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.siam.org\/meetings\/dm16\/\u0022 title=\u0022http:\/\/www.siam.org\/meetings\/dm16\/\u0022\u003Ehttp:\/\/www.siam.org\/meetings\/dm16\/\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003EPosted by Dani Denton\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"466051":{"#nid":"466051","#data":{"type":"event","title":"ARC Colloquium: Martin Farach-Colton - Rutgers University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMartin Farach-Colton - Rutgers University\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 8, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 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\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EA Field Guide to Write Optimization\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003Cbr \/\u003E\u003C\/strong\u003EDictionaries are probably the most widely studied and deployed data structures. \u0026nbsp;For large data, write-optimization techniques allow one to insert records much faster than they can be searched. \u0026nbsp;These new techniques are changing the way such dictionaries are used, which leads to new analytical questions. \u0026nbsp;In this talk, I will survey some of the recent work on write-optimized dictionaries and discuss the impact the new algorithmic work is having in the implementation of storage systems.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio: \u003Cbr \/\u003E\u003C\/strong\u003EMartin Farach-Colton\u0026nbsp;received his MD from Johns Hopkins and his PhD in Computer Science from the University of Maryland. \u0026nbsp;He is a Professor Computer Science at Rutgers University. \u0026nbsp;He is CTO and Co-founder of Tokutek, a database company that was founded to commercialize his research. \u0026nbsp;This company was acquired by\u0026nbsp;Percona in 2015. \u0026nbsp;During 2000-2002, he was a Senior Research Scientist at Google. \u0026nbsp;He works on external memory algorithms as well as their\u0026nbsp;application to storage systems.\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-11-04 12:01:27","changed_gmt":"2017-04-13 21:17:44","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-08T17:00:00-05:00","event_time_end":"2016-02-08T18:00:00-05:00","event_time_end_last":"2016-02-08T18:00:00-05:00","gmt_time_start":"2016-02-08 22:00:00","gmt_time_end":"2016-02-08 23:00:00","gmt_time_end_last":"2016-02-08 23:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"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":""}},"486431":{"#nid":"486431","#data":{"type":"event","title":"ARC Colloquium: Ian Munro - University of Waterloo","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch5 align=\u0022center\u0022\u003EIan Munro \u2013 University of Waterloo\u003C\/h5\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 1, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 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\u003Cstrong\u003ETitle:\u003Cbr \/\u003E \u003C\/strong\u003EOptimal Search Trees with 2-way Comparisons\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003Cbr \/\u003E \u003C\/strong\u003EThis talk is about finding a polynomial time algorithm that you probably thought was known almost a half century ago, but it wasn\u2019t. The polynomial time algorithm is still rather slow and requires a lot of space to solve, so we also look at extremely good and fast approximate solutions. More specifically \u2026\u003Cbr \/\u003E In 1971, Knuth gave an O(n\u003Csup\u003E2\u003C\/sup\u003E)-time algorithm for the now classic problem of finding an optimal binary search tree. Knuth\u2019s algorithm works only for search trees based on 3-way comparisons, but most modern programming languages and computers support only 2-way comparisons (\u0026lt;, = and \u0026gt;). Until this work, the problem of finding an optimal search tree using 2-way comparisons remained open \u2014 polynomial time algorithms were known only for restricted variants. We solve the general case, giving\u003C\/p\u003E\u003Cp\u003E(i)\u0026nbsp; an O(n\u003Csup\u003E4\u003C\/sup\u003E)-time algorithm and\u003C\/p\u003E\u003Cp\u003E(ii) a linear time algorithm that gives a tree with expected search cost within 2 comparisons of the optimal.\u003C\/p\u003E\u003Cp\u003EThis is joint work with Marek Chrobak, Mordecai Golin, and Neal E. Young.\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":"2016-01-14 15:10:33","changed_gmt":"2017-04-13 21:17:09","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-01T12:00:00-05:00","event_time_end":"2016-02-01T13:00:00-05:00","event_time_end_last":"2016-02-01T13:00:00-05:00","gmt_time_start":"2016-02-01 17:00:00","gmt_time_end":"2016-02-01 18:00:00","gmt_time_end_last":"2016-02-01 18: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"},{"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":""}},"486491":{"#nid":"486491","#data":{"type":"event","title":"ARC Colloquium: William Gasarch - University of Maryland at College Park","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EWilliam Gasarch \u2013 University of Maryland\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, February 17, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 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\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EAdvanced Results in the Theory of Languages and Computation which have Simple Proofs\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003Cbr \/\u003E\u003C\/strong\u003EAutomata theory is about the following: Given a language (a set of strings) how hard is it? Is it regular, context free, or decidable? We give three results that COULD be put in a course on such but are not!\u003C\/p\u003E\u003Col\u003E\u003Cli\u003ERegular, Context free, and Decidable languages are closed under many operations. Note the following: if L is regular (CFL) then SUBSEQ(L) is regular (CFL).\u0026nbsp; This is an easy exercise. But what if L is decidable? Is SUBSEQ(L) decidable? The answer may surprise you!\u003C\/li\u003E\u003Cli\u003EThere are languages L that are regular but the DFA for them is much smaller than the CFG for them. How much smaller? The answer may surprise you!\u003C\/li\u003E\u003Cli\u003EIt is easy to show that COL3 \\le COL4 (three-colorability \\le 4-colorablity). Is COL4 \\le COL3? You probably know that it is by going through the Cook-Levin Theorem. Is there an easier proof? The answer would surprise you if I didn\u0027t ask the question so I\u0027ll just say YES- I will show COL4 \\le COL3 with a simple proof.\u003C\/li\u003E\u003C\/ol\u003E\u003Cp\u003EThe answers may surprise you!\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 East at 1 pm"}],"uid":"27466","created_gmt":"2016-01-14 15:29:00","changed_gmt":"2017-04-13 21:17:07","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-17T12:00:00-05:00","event_time_end":"2016-02-17T13:00:00-05:00","event_time_end_last":"2016-02-17T13:00:00-05:00","gmt_time_start":"2016-02-17 17:00:00","gmt_time_end":"2016-02-17 18:00:00","gmt_time_end_last":"2016-02-17 18: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"},{"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":""}},"486601":{"#nid":"486601","#data":{"type":"event","title":"ARC Colloquium: John Wilmes - University of Chicago","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EJohn Wilmes \u2013 University of Chicago\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, January 25, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMiRC 102 A \u0026amp; B - 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\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EThe Isomorphism Problem for Highly Regular Structures\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe Graph Isomorphism (GI) problem has been notorious in computational complexity theory for its unresolved complexity status. Until Babai\u0027s recently announced quasipolynomial-time algorithm for GI, the worst-case time-complexity bound of $\\exp(\\tilde{O}(n^{1\/2}))$ where $n$ is the number of vertices (Babai--Luks, 1983), had stood for over 30 years.\u003C\/p\u003E\u003Cp\u003EAmong the obstacles Babai confronts in his recent breakthrough are primitive coherent configurations (PCCs), a class of highly-regular structures generalizing strongly regular graphs. In this talk, we will describe recent progress characterizing the structure and automorphism groups of PCCs and other highly-regular structures, with applications to GI, and we will describe the connections between these results and Babai\u0027s breakthrough.\u003C\/p\u003E\u003Cp\u003EIn particular, in joint work with Sun, we classify the PCCs with the most automorphisms. In joint work with Babai, Chen, Sun, and Teng, we give the first quasipolynomial-time algorithm for strongly regular GI over an entire interval of the exponent of the degree parameter. And in joint work with Babai, we give a $n^{O(\\log n)}$-time algorithm for the important special case of Steiner Design Isomorphism.\u0026nbsp; In all cases, our progress relies on new structural results we prove, especially on new bounds for the rate of expansion of small sets.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"MIRC 102 A \u0026 B at 1 pm"}],"uid":"27466","created_gmt":"2016-01-14 16:13:25","changed_gmt":"2017-04-13 21:17:07","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-01-25T12:00:00-05:00","event_time_end":"2016-01-25T13:00:00-05:00","event_time_end_last":"2016-01-25T13:00:00-05:00","gmt_time_start":"2016-01-25 17:00:00","gmt_time_end":"2016-01-25 18:00:00","gmt_time_end_last":"2016-01-25 18: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"},{"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":""}},"492641":{"#nid":"492641","#data":{"type":"event","title":"ARC Colloquium: Antonio Blanca - UC Berkeley","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003ENOTE - Talk is at 2 pm instead of 1 pm.\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAntonio Blanca - UC Berkeley\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EFriday, February 5, 2016\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East (not West) - 2:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 3 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003Cbr \/\u003E \u003C\/strong\u003EDynamics for the random-cluster model\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E \u003Cbr \/\u003E The random-cluster model has been widely studied as a unifying framework for random graphs, spin systems and electrical networks, but its dynamics have so far largely resisted analysis. In this talk we present recent results concerning the mixing behavior of natural Markov chains for the random-cluster model in two canonical cases: the mean-field model and the two dimensional lattice graph Z^2. In the mean-field case, we identify a critical regime of the model parameter p in which several natural dynamics undergo an exponential slowdown. In Z^2, we provide tight mixing time bounds for the heat-bath dynamics for all non-critical values of p. These results hold for all values of the second model parameter q \u0026gt; 1.\u003Cbr \/\u003E \u003Cbr \/\u003E Based on joint works with Alistair Sinclair.\u003Cbr \/\u003E \u003Cbr \/\u003E Short Bio: Antonio Blanca is a 5th year PhD student at UC Berkeley advised by Alistair Sinclair. He is interested in algorithms, Markov chain mixing, phase transitions and random structures. He graduated with a BS in Computer Science\/Discrete Math from Georgia Tech.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Talk is at 2 pm instead of 1 pm - Klaus 1116 West"}],"uid":"27466","created_gmt":"2016-01-29 12:48:17","changed_gmt":"2017-04-13 21:16:51","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-05T13:00:00-05:00","event_time_end":"2016-02-05T14:00:00-05:00","event_time_end_last":"2016-02-05T14:00:00-05:00","gmt_time_start":"2016-02-05 18:00:00","gmt_time_end":"2016-02-05 19:00:00","gmt_time_end_last":"2016-02-05 19: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"},{"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":""}},"493111":{"#nid":"493111","#data":{"type":"event","title":"ARC Theory Day","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EARC Theory Day\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 11\u003C\/strong\u003E\u003Cstrong\u003E, 2016\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 - 9:00 am - 4:00 pm\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EObjective:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003EAlgorithms and Randomness Center (ARC) Theory Day is an annual event to showcase lectures on exciting new developments in theoretical computer science. This year\u0027s event features four young speakers who are dedicated to investigating some of the most complex questions in theoretical computer science. These guests will discuss a wide range of topics from interior point methods to circuit lower bounds by random projections. The lectures promise to be engaging and discuss techniques to help solve these emerging problems and understand related phenomena.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EOrganizers:\u003C\/strong\u003E Santosh Vempala, Richard Peng and Dana Randall\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESchedule:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EMonday, April 11, 2016: \u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E9:30 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Breakfast\u003Cbr \/\u003E9:50 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Opening Remarks\u003Cbr \/\u003E10:00 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003EVirginia Vassilevska-Williams\u003C\/strong\u003E (Stanford): \u003Cstrong\u003EFine-Grained Algorithms and Complexity\u003Cbr \/\u003E\u003C\/strong\u003E11:00 am \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Break\u003Cbr \/\u003E11:15 am\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003ERocco Servedio\u003C\/strong\u003E (Columbia): \u003Cstrong\u003ECircuit Lower Bounds via Random Projections\u003Cbr \/\u003E\u003C\/strong\u003E12:15 pm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Lunch Break\u003Cbr \/\u003E1:30 pm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003EAaron Sidford \u003C\/strong\u003E(Microsoft Research): \u003Cstrong\u003ERecent Advances in the Theory of Interior Point Methods\u003Cbr \/\u003E\u003C\/strong\u003E2:30 pm \u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Break\u003Cbr \/\u003E2:45 pm\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003Cstrong\u003ELuca Trevisan\u003C\/strong\u003E (UC Berkeley): \u003Cstrong\u003ERamanujan Graphs\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstracts:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EVirginia Vassilevska-Williams (Stanford): \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003E Fine-Grained Algorithms and Complexity\u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003Cbr \/\u003E \u003C\/strong\u003EA central goal of algorithmic research is to determine how fast computational problems can be solved in the worst case. Theorems from complexity theory state that there are problems that, on inputs of size n, can be solved in t(n) time but not in t(n)^{1-eps} time for eps\u0026gt;0. The main challenge is to determine where in this hierarchy various natural and important problems lie. Throughout the years, many ingenious algorithmic techniques have been developed and applied to obtain blazingly fast algorithms for many problems. Nevertheless, for many other central problems, the best known running times are essentially those of the classical algorithms devised for them in the 1950s and 1960s.\u003Cbr \/\u003E \u003Cbr \/\u003E Unconditional lower bounds seem very difficult to obtain, and so practically all known time lower bounds are conditional. For years, the main tool for proving hardness of computational problems have been NP-hardness reductions, basing hardness on P\\neq NP. However, when we care about the exact running time (as opposed to merely polynomial vs non-polynomial), NP-hardness is not applicable, especially if the running time is already polynomial. In recent years, a new theory has been developed, based on \u201cfine-grained reductions\u201d that focus on exact running times. The goal of these reductions is as follows. Suppose problem A is solvable in a(n) time and problem B in b(n) time, and no a(n)^{1-eps} and b(n)^{1-eps} algorithms are known for A and B respectively. Then, if A is fine-grained reducible to problem B (for a(n) and b(n)), a b(n)^{1-eps} time algorithm for B (for any eps\u0026gt;0) implies an a(n)^{1-eps\u0027} algorithm for A (for some eps\u0027\u0026gt;0). Now, mimicking NP-hardness, the approach is to (1) select a key problem X that is conjectured to require t(n)^{1-o(1)} time for some t, and (2) reduce X in a fine-grained way to many important problems. This approach has led to the discovery of many meaningful relationships between problems, and even sometimes to equivalence classes.\u003Cbr \/\u003E \u003Cbr \/\u003E In this talk I will give an overview or the current progress in this area of study, and will highlight some new exciting developments.\u003Cbr \/\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Virginia V. Williams is an assistant professor of computer science at Stanford University. She obtained her Ph.D. in 2008 from Carnegie Mellon where she was advised by Guy Blelloch. Before joining Stanford, she spent time at the Institute for Advanced Study and UC Berkeley. Her main area of interest is broadly in computational complexity, the design and analysis of algorithms, and more specifically in graph and matrix algorithms.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ERocco Servedio (Columbia University)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003E Circuit Lower Bounds via Random Projections\u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E \u003Cbr \/\u003E Random restrictions are a classical and\u0026nbsp;important technique for proving circuit lower bounds.\u0026nbsp; This talk will discuss\u0026nbsp;\u003Cem\u003Erandom\u0026nbsp;projections,\u0026nbsp;\u003C\/em\u003Ea generalization of random restrictions.\u0026nbsp; While conceptually simple, random projections have led to recent advances on several well-studied lower bound problems involving small-depth circuits.\u0026nbsp; We will see how random projections play a key role in the following results:\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003EAn average-case depth hierarchy theorem for Boolean circuits.\u0026nbsp;This gives an average-case extension of the classical (worst-case) depth hierarchy theorem of\u0026nbsp;Sipser, Yao, and\u0026nbsp;Hastad, and resolves a main open problem in\u0026nbsp;Hastad\u2019s\u0026nbsp;1986 PhD thesis.\u0026nbsp; Via a classical connection between Boolean circuits and structural complexity, this hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, resolving a longstanding conjecture of\u0026nbsp;Hastad,\u0026nbsp;Cai\u0026nbsp;and\u0026nbsp;Babai\u0026nbsp;from the 1980s.\u0026nbsp; (Joint work with Ben\u0026nbsp;Rossman\u0026nbsp;and Li-Yang Tan.)\u003C\/li\u003E\u003Cli\u003EThe first super-polynomial lower bounds against the \u201cdepth d\u0026nbsp;Frege\u201d proof system for some polylogarithmic depth d.\u0026nbsp; Previous super-polynomial lower bounds (Pitassi\u0026nbsp;et al. 1993,\u0026nbsp;Krajicek\u0026nbsp;et al. 1995) were only known against depth-d\u0026nbsp;Frege\u0026nbsp;for d=Theta(log log n).\u0026nbsp; (Joint work with Toni\u0026nbsp;Pitassi, Ben\u0026nbsp;Rossman, and Li-Yang Tan.)\u003C\/li\u003E\u003Cli\u003EA nearly optimal size lower bound on small-depth circuits that determine whether a graph has a short s-to-t path.\u0026nbsp; We show that depth-d circuits for distance-k connectivity on n-node graphs must have size n^{\\Omega(k^{1\/d}\/d)}; the previous best size lower bounds for this problem were n^{k^{\\exp(-O(d))}} (due to\u0026nbsp;Beame\u0026nbsp;et al. 1998) and n^{\\Omega((\\log k)\/d)} (due to\u0026nbsp;Rossman\u0026nbsp;2014).\u0026nbsp; (Joint work with Xi Chen, Igor Oliveira and Li-Yang Tan.)\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003E Rocco Servedio is an Associate Professor of Computer Science at Columbia University. His research interests center around computational learning theory, property testing, and computational complexity.\u0026nbsp; Rocco is the recipient of an NSF Career Award and a Sloan Foundation Fellowship; his research has received Best Paper \/ Best Student Paper awards from the CCC, COLT, FOCS, and STOC conferences.\u0026nbsp; His teaching at Columbia has been recognized with the Department of Computer Science Distinguished Teaching Award, the Columbia Engineering Alumni Association Distinguished Faculty Teaching Award, and the Columbia Presidential Teaching Award.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAaron Sidford (Microsoft Research)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: \u003Cbr \/\u003E Recent Advances in the Theory of Interior Point Methods\u0026nbsp;\u003Cbr \/\u003E \u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u0026nbsp;\u003Cbr \/\u003E In this talk I will survey recent results on\u0026nbsp;using interior point techniques\u0026nbsp;to design provably efficient algorithms. I will give a brief overview of this powerful convex optimization technique and discuss how it has been used to improve the running time of fundamental optimization problems such as maximum flow, linear programming, and most recently the geometric median problem. In particular, I will highlight recent joint work with Michael Cohen, Yin Tat Lee, Jakub Pachocki, and Gary Miller building on these techniques to obtain the first nearly linear time algorithm for computing the geometric median. No previous experience with interior point methods required.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio\u003C\/strong\u003E:\u0026nbsp;\u003Cbr \/\u003E Aaron Sidford is a postdoctoral researcher at Microsoft Research New England and will be joining the department of Management Science and Engineering at Stanford University in Fall 2016. Aaron received his PhD from the EECS department at MIT where he was advised by Professor Jonathan Kelner.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003EAaron\u2019s research interests lie broadly in the theory of computation and the design and analysis of algorithms. He is particularly interested in work at the intersection of continuous optimization, graph theory, numerical linear algebra, and data structures.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELuca Trevisan (UC Berkeley)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003E Ramanujan Graphs\u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E \u003Cbr \/\u003E We will review what is known about existence and constructions of Ramanujan graphs, which are the best possible expander graphs from the point of view of spectral expansion.\u003Cbr \/\u003E We will talk about Friedman\u0027s result that random graphs are nearly Ramanujan, and recent simplifications of his proof, about a characterization of Ramanujan graphs in terms of the Ihara zeta function, about number-theoretic efficient constructions, and about the recent non-constructive existence results of Marcus, Spielman, and Srivastava.\u003Cbr \/\u003E \u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Luca Trevisan is a professor of Electrical Engineering and Computer Sciences and of Mathematics at U.C. Berkeley, and a senior scientist at the Simons Institute for the Theory of Computing. In the past, he has also taught at Columbia University and at Stanford. He is interested in several aspects of computational complexity theory and, in the last few years, he has been working on spectral graph theory.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 East \u0026 West - Invited Speakers: Rocco Servedio (Columbia), Aaron Sidford (Microsoft Research), Luca Trevisan (UC Berkeley) and Virginia Vassilevska-Williams (Stanford)"}],"uid":"27466","created_gmt":"2016-01-31 16:15:32","changed_gmt":"2017-04-13 21:16:50","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-04-11T10:30:00-04:00","event_time_end":"2016-04-11T17:00:00-04:00","event_time_end_last":"2016-04-11T17:00:00-04:00","gmt_time_start":"2016-04-11 14:30:00","gmt_time_end":"2016-04-11 21:00:00","gmt_time_end_last":"2016-04-11 21: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"},{"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":""}},"500221":{"#nid":"500221","#data":{"type":"event","title":"ARC Colloquium: Marco-Dick Yun Kuen Cheung - University of Vienna","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMarco-Dick Yun Kuen Cheung \u0026nbsp;- University of Vienna\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 29, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 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\u003Cstrong\u003ETitle: \u003Cbr \/\u003E \u003C\/strong\u003EGraph Minors for Preserving Terminal Distances Approximately\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003Cbr \/\u003E \u003C\/strong\u003EGiven a graph where vertices are partitioned into k terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion.\u0026nbsp; This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed.\u003Cbr \/\u003E \u003Cbr \/\u003E We introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than 2 \/ 2.5\/ 3\u0026nbsp; must have \\Omega(k^2) \/ \\Omega(k^{5\/4}) \/ \\Omega(k^{6\/5}) non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any linear (in k) non-terminals will \u003Cem\u003Enot\u003C\/em\u003E help improving the lower bound to a constant.\u003Cbr \/\u003E \u003Cbr \/\u003E We also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with $1+epsilon$ distortion and O(k^2 log^2 k \/ epsilon^2) non-terminals.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\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":"2016-02-15 10:03:04","changed_gmt":"2017-04-13 21:16:39","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-29T12:00:00-05:00","event_time_end":"2016-02-29T13:00:00-05:00","event_time_end_last":"2016-02-29T13:00:00-05:00","gmt_time_start":"2016-02-29 17:00:00","gmt_time_end":"2016-02-29 18:00:00","gmt_time_end_last":"2016-02-29 18: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"},{"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":""}},"500231":{"#nid":"500231","#data":{"type":"event","title":"ARC Colloquium: Alon Orlitsky - University of CA, San Diego","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlon Orlitsky - University of CA, San Diego\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 18, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 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\u003Cstrong\u003ETitle:\u0026nbsp;\u003Cbr \/\u003E\u003C\/strong\u003ELearning and Forecasting over Large Domains: The Art of the Doable\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003Cbr \/\u003E \u003C\/strong\u003ELearning a distribution and forecasting its outcomes are important tasks whose complexity increases with the distribution\u0027s support size. We consider useful and natural formulations of these two tasks that allow them to be performed with a sample whose size is fixed and independent of the distribution or its support size.\u003Cbr \/\u003E \u003Cbr \/\u003E Learning a distribution to a given KL divergence requires a sample size that increases linearly with the support size. We show that with n samples, the distribution can be learned to a KL divergence that is at most 1\/sqrt(n) higher than that achievable by any estimator, even one that knows the distribution up to permutation.\u003Cbr \/\u003E \u003Cbr \/\u003E Estimating a distribution\u0027s support size may require an unbounded number samples. Yet we show that with n samples, we can estimate the number of hitherto unseen elements that will be observed in up to n*log(n) new samples, thereby estimating the effective support of a much larger sample.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E Joint work with Ananda Theertha Suresh and Yihong Wu.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Alon Orlitsky received B.Sc. degrees in Mathematics and Electrical Engineering from Ben Gurion University in 1980 and 1981, and M.Sc. and Ph.D. degrees in Electrical Engineering from Stanford University in 1982 and 1986.\u003Cbr \/\u003E \u003Cbr \/\u003E From 1986 to 1996 he was with the Communications Analysis Research Department of Bell Laboratories. He spent the following year as a quantitative analyst at D.E. Shaw and Company, an investment firm in New York City. In 1997 he joined the University of California San Diego, where he is currently a professor of Electrical and Computer Engineering and of Computer Science and Engineering.\u0026nbsp; His research concerns information theory, statistical modeling, and machine learning.\u003Cbr \/\u003E \u003Cbr \/\u003E From 2011 to 2014 Alon directed UCSD\u0027s Center for Wireless Communications, and since 2006 he has directed the Information Theory and Applications Center. He is currently the president of the Information Theory Society. He has co-organized numerous programs on information theory, machine learning, and statistics, including the Information Theory and Applications Workshop that he started in 2006 and has helped organize since.\u003Cbr \/\u003E \u003Cbr \/\u003E Alon is a recipient of the 1981 ITT International Fellowship and the 1992 IEEE W.R.G. Baker Paper Award, and co-recipient of the 2006 Information Theory Society Paper Award and the 2016 NIPS Paper Award. He is a fellow of the IEEE, and holds the Qualcomm Chair for Information Theory and its Applications at UCSD.\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EURL:\u003C\/strong\u003E \u003Ca href=\u0022http:\/\/alon.ucsd.edu\/\u0022\u003Ehttp:\/\/alon.ucsd.edu\/\u003C\/a\u003E\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EHost:\u003C\/strong\u003E Vijay Vazirani (\u003Ca href=\u0022mailto:vazirani@cc.gatech.edu\u0022\u003Evazirani@cc.gatech.edu\u003C\/a\u003E)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\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":"2016-02-15 10:09:58","changed_gmt":"2017-04-13 21:16:39","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-04-18T14:00:00-04:00","event_time_end":"2016-04-18T15:00:00-04:00","event_time_end_last":"2016-04-18T15:00:00-04:00","gmt_time_start":"2016-04-18 18:00:00","gmt_time_end":"2016-04-18 19:00:00","gmt_time_end_last":"2016-04-18 19: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"},{"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":""}},"503471":{"#nid":"503471","#data":{"type":"event","title":"ARC Colloquium: Ilya Safro - Clemson University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EIlya Safro - Clemson University\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 7, 20116\u003Cbr \/\u003EKlaus 1116 West - 1:00 pm\u003Cbr \/\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EMultiscale Methods for Discrete Optimization on Graphs\u003Cbr \/\u003E\u003Cstrong\u003EAbstract: \u003Cbr \/\u003E\u003C\/strong\u003EIn many real-world problems, a big scale gap can be observed between micro- and macroscopic scales of the problem because of the difference in mathematical (engineering, social, biological, physical, etc.) models and\/or laws at different scales. The main objective of multigrid-inspired multiscale algorithms is to create a hierarchy of problems, each representing the original problem at different coarse scales with fewer degrees of freedom. We will discuss different strategies of creating these hierarchies for discrete optimization problems on large-scale graphs. These strategies are inspired by the classical multigrid frameworks such as geometric multigrid, algebraic multigrid and full approximation scheme. We will present in details a multiscale framework for linear arrangement, network compression, k-partitioning and clustering, network generation, sparsification, and epidemics response problems. Time permits, a multigrid-inspired algorithm for the support vector machines will be presented.\u003C\/p\u003E\u003Cp\u003EUrl: \u003Ca href=\u0022http:\/\/people.cs.clemson.edu\/~isafro\/\u0022\u003Ehttp:\/\/people.cs.clemson.edu\/~isafro\/\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003EHost: Richard Peng (\u003Ca href=\u0022mailto:rpeng@cc.gatech.edu\u0022\u003Erpeng@cc.gatech.edu\u003C\/a\u003E)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\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":"2016-02-19 10:55:09","changed_gmt":"2017-04-13 21:16:35","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-03-07T12:00:00-05:00","event_time_end":"2016-03-07T13:00:00-05:00","event_time_end_last":"2016-03-07T13:00:00-05:00","gmt_time_start":"2016-03-07 17:00:00","gmt_time_end":"2016-03-07 18:00:00","gmt_time_end_last":"2016-03-07 18: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"},{"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":""}},"517551":{"#nid":"517551","#data":{"type":"event","title":"ARC Colloquium: Amit Sahai - UCLA","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAmit Sahai\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EFriday, April 15, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 2:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus Atrium at 3 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003Cbr \/\u003E\u003C\/strong\u003EHiding Secrets in Software\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003Cbr \/\u003EThe goal of general-purpose program obfuscation is to make an arbitrary computer program \u201cunintelligible\u201d while preserving its functionality. Obfuscation allows us to achieve a powerful capability: software that can keep a secret. This talk will cover recent advances in obfuscation research, yielding constructions of general-purpose obfuscation mechanisms based on new mathematical structures.\u003Cstrong\u003E\u003Cbr \/\u003EBio: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EProfessor Amit Sahai received his Ph.D. in Computer Science from MIT in 2000. From 2000 to 2004, he was on the faculty at Princeton University; in 2004 he joined UCLA, where he currently holds the position of Professor of Computer Science. His research interests are in security and cryptography, and theoretical computer science more broadly. He is the co-inventor of Attribute-Based Encryption, Functional Encryption, and Indistinguishability Obfuscation. He has published more than 100 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. He has given a number of invited talks at institutions such as MIT, Stanford, and Berkeley, including the 2004 Distinguished Cryptographer Lecture Series at NTT Labs, Japan. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, received an Okawa Research Grant Award in 2007, a Xerox Foundation Faculty Award in 2010, a Google Faculty Research Award in 2010, and a 2012 Pazy Memorial Award. He was awarded the 2016 Lockheed Martin Excellence in Teaching Award. His research has been covered by several news agencies including the BBC World Service, Quanta Magazine, Wired, and IEEE Spectrum.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EUrl:\u003C\/strong\u003E \u003Ca href=\u0022http:\/\/web.cs.ucla.edu\/~sahai\/\u0022 title=\u0022http:\/\/web.cs.ucla.edu\/~sahai\/\u0022\u003Ehttp:\/\/web.cs.ucla.edu\/~sahai\/\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EHost:\u003C\/strong\u003E Lance Fortnow (\u003Ca href=\u0022mailto:fortnow@cc.gatech.edu\u0022\u003Efortnow@cc.gatech.edu\u003C\/a\u003E)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Talk is at 2 pm instead of 1 pm - Klaus 1116 West"}],"uid":"27466","created_gmt":"2016-03-25 11:18:57","changed_gmt":"2017-04-13 21:16:11","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-04-15T15:00:00-04:00","event_time_end":"2016-04-15T16:00:00-04:00","event_time_end_last":"2016-04-15T16:00:00-04:00","gmt_time_start":"2016-04-15 19:00:00","gmt_time_end":"2016-04-15 20:00:00","gmt_time_end_last":"2016-04-15 20: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"},{"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":""}},"542021":{"#nid":"542021","#data":{"type":"event","title":"ARC Talk: David Woodruff - IBM","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EDavid Woodruff - IBM\u003Cbr \/\u003E\u003C\/strong\u003E\u003Cstrong\u003ETuesday, June 7, 2016\u003Cbr \/\u003E\u003C\/strong\u003E\u003Cstrong\u003EKlaus Conference Room 2100 - 2:00 pm\u003C\/strong\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003Cbr \/\u003E\u003C\/strong\u003EAn Optimal Algorithm for Finding L2 Heavy Hitters\u003Cbr \/\u003E\u003Cbr \/\u003E\u003Cstrong\u003EAbstract:\u003Cbr \/\u003E\u003C\/strong\u003EWe consider the problem of finding the most frequent items in a stream of items from a universe of size n. Namely, we consider returning all l_2-heavy hitters, i.e., those items j for which f_j \u0026gt;= eps sqrt{F_2}, where f_j is the number of occurrences of item j, and F_2 = sum_i f_i^2 is the second moment of the stream. In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch data structure, which solves this using log^2 n bits of space (for constant eps). The only known lower bound is log n bits. Using Gaussian processes, we show it is possible to achieve an optimal log n bits of space. Our technique resolves a number of other questions in data streams.\u003C\/p\u003E\u003Cp\u003EBased on work with Vladimir Braverman, Stephen Chestnut, and Nikita Ivkin (STOC \u002716) and work with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Jelani Nelson, and Zhengyu Wang.\u003Cbr \/\u003E\u003Cbr \/\u003EHost: Santosh Vempala\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 2100 at 2 pm"}],"uid":"27466","created_gmt":"2016-06-06 09:20:02","changed_gmt":"2017-04-13 21:15:40","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-06-07T15:00:00-04:00","event_time_end":"2016-06-07T16:00:00-04:00","event_time_end_last":"2016-06-07T16:00:00-04:00","gmt_time_start":"2016-06-07 19:00:00","gmt_time_end":"2016-06-07 20:00:00","gmt_time_end_last":"2016-06-07 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"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\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"550161":{"#nid":"550161","#data":{"type":"event","title":"ARC Colloquium:  Shayan Oveis Gharan (Washington)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/55876\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/55876\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\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:\/\/homes.cs.washington.edu\/~shayan\/\u0022\u003E\u003Cstrong\u003EShayan Oveis Gharan \u0026ndash; \u003C\/strong\u003E\u003Cstrong\u003EUniversity of Washington\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp  align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 12, 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\u003Cem\u003EStrongly Rayleigh distributions and their Applications in Algorithm Design\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EA multivariate polynomial p(z1,...,zn) is stable if p(z1,...,zn) \u0026lt;\u0026gt; 0 whenever Im(zi)\u0026gt;0 for all i. Strongly Rayleigh distributions are probability distributions on 0-1 random variables whose generating polynomial is stable. They can be seen as a natural generalization of product distributions.\u0026nbsp;Borcea, Branden and Liggett used\u0026nbsp;the geometry of stable polynomials to prove numerous properties of strongly Rayleigh distributions,\u0026nbsp;including negative association, and closure under conditioning and truncation.\u003Cbr \/\u003E\r\nIn this talk I will go over basic properties of these distributions, and then I will describe several algorithmic applications.\u003Cbr \/\u003E\r\nBased on joint works with Nima Anari, Alireza Rezaei,\u0026nbsp;Mohit Singh, Amin Saberi.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EShayan Oveis Gharan is an assistant professor in the \u003Ca href=\u0022https:\/\/www.cs.washington.edu\u0022\u003Ecomputer science and engineering\u003C\/a\u003E department at \u003Ca href=\u0022http:\/\/uw.edu\u0022\u003EUniversity of Washington\u003C\/a\u003E.\u0026nbsp; He received his PhD from the \u003Ca href=\u0022http:\/\/msande.stanford.edu\u0022\u003EMS\u0026amp;E department\u003C\/a\u003E at \u003Ca href=\u0022http:\/\/stanford.edu\u0022\u003EStanford University\u003C\/a\u003E in 2013 advised by \u003Ca href=\u0022http:\/\/stanford.edu\/%7Esaberi%22\u0022\u003EAmin Saberi\u003C\/a\u003E and \u003Ca href=\u0022http:\/\/www.eecs.berkeley.edu\/%7Eluca\/\u0022\u003ELuca Trevisan\u003C\/a\u003E.\u0026nbsp; Before joining \u003Ca href=\u0022http:\/\/www.washington.edu\/\u0022\u003EUW\u003C\/a\u003E he spent one and a half years as a postdoctoral \u003Ca href=\u0022http:\/\/millerinstitute.berkeley.edu\u0022\u003EMiller Fellow\u003C\/a\u003E at \u003Ca href=\u0022http:\/\/www.berkeley.edu\/\u0022\u003EUC Berkeley\u003C\/a\u003E where his host was \u003Ca href=\u0022http:\/\/www.cs.berkeley.edu\/%7Evazirani\/\u0022\u003EUmesh Vazirani\u003C\/a\u003E. He did his undergraduate studies at the \u003Ca href=\u0022http:\/\/ce.sharif.edu\u0022\u003EComputer Engineering department\u003C\/a\u003E at \u003Ca href=\u0022http:\/\/sharif.edu\u0022\u003ESharif University\u003C\/a\u003E.\u003Cbr \/\u003E\r\nShayan\u0026#39;s research includes Algorithm design, Graph Theory and Applied Probability.\u0026nbsp; He received ACM doctoral dissertation award honorable mention for his PhD thesis \u0026quot;New Rounding Techniques for the Design and Analysis of Approximation Algorithms\u0026quot; in 2013. He and his coauthors received best paper awards at SODA 2010 and FOCS 2011 for their works on the Traveling Salesman Problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/homes.cs.washington.edu\/~shayan\/\u0022\u003Ehttp:\/\/homes.cs.washington.edu\/~shayan\/\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Strongly Rayleigh distributions and their Applications in Algorithm Design (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-07-01 15:50:54","changed_gmt":"2017-04-13 21:15:26","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-09-12T12:00:00-04:00","event_time_end":"2016-09-12T13:00:00-04:00","event_time_end_last":"2016-09-12T13:00:00-04:00","gmt_time_start":"2016-09-12 16:00:00","gmt_time_end":"2016-09-12 17:00:00","gmt_time_end_last":"2016-09-12 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/homes.cs.washington.edu\/~shayan\/","title":"Shayan Oveis Gharan"}],"groups":[{"id":"70263","name":"ARC"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[{"id":"92341","name":"Algorithms 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":""}},"553001":{"#nid":"553001","#data":{"type":"event","title":"ARC Colloquium: Brendan Lucier (Microsoft Research)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/55928\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/55928\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\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\u003Cstrong\u003E\u003Ca href=\u0022http:\/\/research.microsoft.com\/en-us\/um\/people\/brlucier\/\u0022\u003EBrendan Lucier\u003C\/a\u003E \u0026ndash; Microsoft Research\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 3, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nPrices, Auctions, and Combinatorial Prophet Inequalities\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nThe most common way to sell resources, from apples to business licenses to concert tickets, is to post prices. A choice of prices can be viewed as an algorithm for an online stochastic optimization problem, which makes decisions using value thresholds. This connection provides an opportunity to use the famous prophet inequality -- which describes the power of threshold rules -- to study pricing problems, and vice-versa. In this talk I\u0026#39;ll present a general framework for deriving new prophet inequalities using economic insights from pricing, with algorithmic applications. Along the way, I\u0026#39;ll describe an unexpected connection between posted prices and equilibria of non-truthful auctions.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased on joint works with Paul Duetting, Michal Feldman, Nick Gravin, and Thomas Kesselheim.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nBrendan Lucier is a Researcher at Microsoft Research, New England. Prior to joining Microsoft, he received his Ph.D. in Computer Science from the University of Toronto. His research interests lie in the intersection of theoretical Computer Science and Economics, and include algorithmic market design, algorithmic pricing, and social processes on networks. He is especially interested in the tradeoffs between simplicity, robustness, and optimality in markets for complex goods and services.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/research.microsoft.com\/en-us\/um\/people\/brlucier\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/hg\/item\/553001\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","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Prices, Auctions, and Combinatorial Prophet Inequalities (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-07-15 07:55:08","changed_gmt":"2017-04-13 21:15:23","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-10-03T12:00:00-04:00","event_time_end":"2016-10-03T13:00:00-04:00","event_time_end_last":"2016-10-03T13:00:00-04:00","gmt_time_start":"2016-10-03 16:00:00","gmt_time_end":"2016-10-03 17:00:00","gmt_time_end_last":"2016-10-03 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"},{"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":"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":"Dani Denton \r\n","format":"plain_text"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"560051":{"#nid":"560051","#data":{"type":"event","title":"ARC Colloquium: David Karger (MIT)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/55915\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/55915\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\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:\/\/people.csail.mit.edu\/karger\/\u0022\u003E\u003Cstrong\u003EDavid Karger - MIT\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 26, 2016\u003Cbr \/\u003E\r\nKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nA Fast and Simple Unbiased Estimator for Network (Un)reliability\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nThe following procedure yields an unbiased estimator for the disconnection probability of an n-vertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every edge independently with probability 1-n^{-2\/c}, then (ii) recursively compute the disconnection probability of the resulting tiny graph if each edge fails with probability n^{2\/c}p.\u0026nbsp; We give a short, simple, self-contained proof that this estimator can be computed in linear time and has relative variance O(n^2).\u0026nbsp; Combining these two facts with a relatively standard sparsification argument yields an O(n^3\\log n)-time algorithm for estimating the (un)reliability of a network.\u0026nbsp; We also show how the technique can be used to create unbiased samples of disconnected networks.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESpeaker\u0026#39;s webpage: \u003Ca href=\u0022http:\/\/people.csail.mit.edu\/karger\/\u0022\u003Ehttp:\/\/people.csail.mit.edu\/karger\/\u003C\/a\u003E\u003Cbr \/\u003E\r\nFall 2016 ARC Seminar Schedule: \u0026nbsp;\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/114\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/114\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":"A Fast and Simple Unbiased Estimator for Network (Un)reliability (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-08 10:29:12","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-09-26T12:00:00-04:00","event_time_end":"2016-09-26T13:00:00-04:00","event_time_end_last":"2016-09-26T13:00:00-04:00","gmt_time_start":"2016-09-26 16:00:00","gmt_time_end":"2016-09-26 17:00:00","gmt_time_end_last":"2016-09-26 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"50875","name":"School of Computer Science"}],"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":"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":""}},"560071":{"#nid":"560071","#data":{"type":"event","title":"ARC Colloquium: Ankur Moitra (MIT)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/56016\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/56016\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:\/\/people.csail.mit.edu\/moitra\/\u0022\u003E\u003Cstrong\u003EAnkur Moitra - MIT\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 31, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West \u0026ndash; 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nRobust Statistics, Revisited\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nStarting from the seminal works of Tukey (1960) and Huber (1962), the field of robust statistics asks: Are there estimators that provable work in the presence of noise? The trouble is that all known provably robust estimators are also hard to compute in high-dimensions.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EHere, we study a basic problem in robust statistics, posed in various forms in the above works. Given corrupted samples from a high-dimensional Gaussian, are there efficient algorithms to accurately estimate its parameters? We give the first algorithms that are able to tolerate a constant fraction of corruptions that is independent of the dimension. Additionally, we give several more applications of our techniques to product distributions and various mixture models.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is based on joint work with Ilias Diakonikolas, Jerry Li, Gautam Kamath, Daniel Kane and Alistair Stewart.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nAnkur Moitra is the Rockwell International Assistant Professor in the Department of Mathematics at MIT and a Principal Investigator in the Computer Science and Artificial Intelligence Lab (CSAIL). The aim of his work is to bridge the gap between theoretical computer science and machine learning by developing algorithms with provable guarantees and foundations for reasoning about their behavior. He is a recipient of a Packard Fellowship, a Sloan Fellowship, an NSF CAREER Award, an NSF Computing and Innovation Fellowship and a Hertz Fellowship.\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":"Revisiting Robust Statistics (Klaus 1116 West at 11am)"}],"uid":"27466","created_gmt":"2016-08-08 10:33:20","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-10-31T12:00:00-04:00","event_time_end":"2016-10-31T13:00:00-04:00","event_time_end_last":"2016-10-31T13:00:00-04:00","gmt_time_start":"2016-10-31 16:00:00","gmt_time_end":"2016-10-31 17:00:00","gmt_time_end_last":"2016-10-31 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":""}},"560081":{"#nid":"560081","#data":{"type":"event","title":"ARC Colloquium: David Zuckerman (UT Austin)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/56062\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/56062\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=\u0022https:\/\/www.cs.utexas.edu\/~diz\/\u0022\u003E\u003Cstrong\u003EDavid Zuckerman \u0026ndash; UT Austin\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 14, 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\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003EExplicit Two-Source Extractors and Resilient Functions\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u0026nbsp;\u003Cbr \/\u003E\r\nWe explicitly construct an extractor for two independent sources on n bits, each with min-entropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{-\\Omega(1)}. The best previous extractor, by Bourgain, required each source to have min-entropy .499n.\u003Cbr \/\u003E\r\nA key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on n bits that is resilient to coalitions of size n^{1-delta}, for any delta\u0026gt;0. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on n bits, where some unknown n-q bits are chosen almost polylog(n)-wise independently, and the remaining q=n^{1-\\delta} bits are chosen by an adversary as an arbitrary function of the n-q bits. The best previous construction, by Viola, achieved q=n^{1\/2 - \\delta}.\u003Cbr \/\u003E\r\nOur explicit two-source extractor directly implies an explicit construction of a 2^{(log log N)^{O(1)}}-Ramsey graph over N vertices, improving bounds obtained by Barak et al. and matching independent work by Cohen.\u003Cbr \/\u003E\r\nJoint work with Eshan Chattopadhyay.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u0026nbsp;\u0026nbsp;\u003C\/strong\u003E\u003Cbr \/\u003E\r\nDavid Zuckerman holds an Endowed Professorship in the Computer Science Department at the \u003Ca href=\u0022http:\/\/www.cs.utexas.edu\u0022\u003EUniversity of Texas at Austin\u003C\/a\u003E. He received an A.B. in Mathematics from Harvard University in 1987 and a Ph.D. in Computer Science from U.C. Berkeley in 1991. He was a postdoctoral fellow at MIT from 1991-1993, and at Hebrew University in the Fall of 1993. He has been with the University of Texas since then, visiting U.C. Berkeley from 1999-2000, Harvard University from 2004-2005, and the Institute for Advanced Study from 2011-12.\u003Cbr \/\u003E\r\nHis research focuses primarily on pseudorandomness and the role of randomness in computing. He is best known for his work on randomness extractors and their applications. His other research interests include coding theory, distributed computing, cryptography, inapproximability, and other areas of complexity theory. His research awards include a \u003Ca href=\u0022https:\/\/www.simonsfoundation.org\/mathematics-and-physical-science\/simons-investigators\/simons-investigators-awardees\/\u0022\u003ESimons Investigator Award\u003C\/a\u003E, a Best Paper Award at STOC 2016, ACM Fellow, a Guggenheim Fellowship, a Packard Fellowship for Science and Engineering, a Sloan Research Fellowship, and an NSF Young Investigator Award.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/www.cs.utexas.edu\/~diz\/\u0022\u003Ehttp:\/\/www.cs.utexas.edu\/~diz\/\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Explicit Two-Source Extractors and Resilient Functions (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-08 10:35:24","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-14T11:00:00-05:00","event_time_end":"2016-11-14T12:00:00-05:00","event_time_end_last":"2016-11-14T12:00:00-05:00","gmt_time_start":"2016-11-14 16:00:00","gmt_time_end":"2016-11-14 17:00:00","gmt_time_end_last":"2016-11-14 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"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":"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\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"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":""}},"560251":{"#nid":"560251","#data":{"type":"event","title":"ARC-IDEaS Distinguished Lecture: Jon Kleinberg (Cornell)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/56012\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/56012\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\r\n\r\n\u003Cp  align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) and\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EInstitute for Data Engineering and Science (IDEaS) present\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EARC-IDEaS Distinguished Lecture\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch2 align=\u0022center\u0022\u003E\u003Cstrong\u003EJon Kleinberg - Cornell University\u003C\/strong\u003E\u003C\/h2\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 24, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 at 10 am\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch2 align=\u0022center\u0022\u003E\u003Cem\u003EHuman Decisions and Machine Predictions\u003C\/em\u003E\u003C\/h2\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nAn increasing number of domains are providing us with detailed trace data on human decisions, often made by experts with deep experience in the subject matter. This provides an opportunity to use machine-learning prediction algorithms to ask several families of questions --- not only about the extent to which algorithms can outperform expert-level human decision-making in specific domains, but also whether we can use algorithms to analyze the nature of the errors made by human experts, to predict which instances will be hardest for these experts, and to explore some of the ways in which prediction algorithms can serve as supplements to human decision-making in different applications.\u0026nbsp;\u0026nbsp;In this talk, I\u0026#39;ll explore this theme by drawing on a line of recent projects; all are joint with Sendhil Mullainathan, and include collaborations with Ashton Anderson, Himabindu Lakkaraju, Jure Leskovec, Annie Liang, and Jens Ludwig.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nJon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Science; and he is the recipient of research fellowships from the MacArthur, Packard, Simons, and Sloan Foundations, as well as awards including the Nevanlinna Prize, the Harvey Prize, the Newell Award, and the ACM-Infosys Foundation Award in the Computing Sciences.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EKlaus 1116 at 10am\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"Nevanlinna Prize winner Jon Kleinberg speaking on Human Decisions and Machine Predictions (Klaus 1116 at 10 am)"}],"uid":"27466","created_gmt":"2016-08-08 13:58:43","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-10-24T10:30:00-04:00","event_time_end":"2016-10-24T13:30:00-04:00","event_time_end_last":"2016-10-24T13:30:00-04:00","gmt_time_start":"2016-10-24 14:30:00","gmt_time_end":"2016-10-24 17:30:00","gmt_time_end_last":"2016-10-24 17:30: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"},{"id":"168719","name":"ARC-IDEaS Distinguished Lecture"},{"id":"168718","name":"ARC10"}],"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":""}},"563101":{"#nid":"563101","#data":{"type":"event","title":"ARC Colloquium: Sofya Raskhodnikova (Penn State)","body":[{"value":"\r\n\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/56017\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/56017\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:\/\/www.cse.psu.edu\/~sxr48\/\u0022\u003E\u003Cstrong\u003ESofya Raskhodnikova - Penn State\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 7, 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:\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003EDifferentially Private Analysis of Graphs\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nMany types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing \u0026ldquo;friendships\u0026rdquo; in an online social network, financial transactions, email communication, doctor-patient relationships, and romantic ties. On one hand, such datasets contain sensitive information about individuals. On the other hand, global information that can be gleaned from their analysis can provide significant benefits to society. Several naive attempts at anonymizing sensitive data by stripping obvious identifying information resulted in spectacular failures. In this talk, we discuss algorithms for analyzing network data that satisfy a rigourous notion of privacy called\u003Cem\u003E\u0026nbsp;node differential privacy\u003C\/em\u003E. We present several techniques for designing node differentially private algorithms, based on combinatorial analysis, network flow, and linear and convex programming.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased on joint work with A. Smith (FOCS 2016) and with S. Kasiwisvanathan, K. Nissim, A. Smith (TCC 2013)\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Ca href=\u0022http:\/\/www.cse.psu.edu\/~sofya\/\u0022 target=\u0022_blank\u0022\u003ESofya\u0026nbsp;Raskhodnikova\u003C\/a\u003E\u0026nbsp;is an associate professor of Computer Science and Engineering at Penn State. Her research interests include sublinear-time algorithms, private data analysis, approximation algorithms, and randomized algorithms. She got her PhD from MIT in 2003. She has held visiting positions at\u0026nbsp;\u003Ca href=\u0022http:\/\/www.huji.ac.il\/\u0022 target=\u0022_blank\u0022\u003Ethe Hebrew University of Jerusalem\u003C\/a\u003E,\u0026nbsp;\u003Ca href=\u0022http:\/\/www.weizmann.ac.il\/\u0022 target=\u0022_blank\u0022\u003Ethe Weizmann Institute of Science\u003C\/a\u003E,\u0026nbsp;\u003Ca href=\u0022http:\/\/www.ipam.ucla.edu\/\u0022 target=\u0022_blank\u0022\u003Ethe Institute for Pure and Applied Mathematics\u003C\/a\u003E,\u0026nbsp;\u003Ca href=\u0022http:\/\/www.bu.edu\/cs\/busec\/people\/\u0022 target=\u0022_blank\u0022\u003EBoston University\u003C\/a\u003E\u0026nbsp;and\u0026nbsp;\u003Ca href=\u0022http:\/\/www.seas.harvard.edu\/computer-science\u0022 target=\u0022_blank\u0022\u003EHarvard University\u003C\/a\u003E.\u0026nbsp;\u003Cbr \/\u003E\r\nSpeaker\u0026#39;s webpage: \u003Ca href=\u0022http:\/\/www.cse.psu.edu\/~sofya\/\u0022 target=\u0022_blank\u0022\u003ESofya Raskhodnikova\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Differentially Private Analysis of Graphs (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-16 10:16:58","changed_gmt":"2017-04-13 21:15:07","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-11-07T11:00:00-05:00","event_time_end":"2016-11-07T12:00:00-05:00","event_time_end_last":"2016-11-07T12:00:00-05:00","gmt_time_start":"2016-11-07 16:00:00","gmt_time_end":"2016-11-07 17:00:00","gmt_time_end_last":"2016-11-07 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\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"564791":{"#nid":"564791","#data":{"type":"event","title":"ARC Colloquium: Alina Ene (Boston University)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/55973\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/55973\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\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-people.bu.edu\/aene\/\u0022\u003E\u003Cstrong\u003EAlina Ene - Boston University\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 17, 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:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nFrom Minimum\u0026nbsp;Cut\u0026nbsp;to Submodular Minimization: Leveraging the Decomposable Structure\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nSubmodular function minimization is a fundamental optimization problem that arises in several applications in machine learning and computer vision. The problem is known to be solvable in polynomial time, but general purpose algorithms have high running times and are unsuitable for large-scale problems. Recent work aims to obtain very practical algorithms for minimizing functions that are sums of \u0026quot;simple\u0026quot; functions. This class of functions provides an important bridge between functions with a rich combinatorial structure \u0026ndash; notably, the\u0026nbsp;cut\u0026nbsp;function of a graph\u0026nbsp;\u0026ndash; and general submodular functions, and it brings along powerful combinatorial structure reminiscent of\u0026nbsp;graphs\u0026nbsp;as well as a fair bit of modeling power that greatly expands its applications. In this talk, we describe recent progress on designing very efficient algorithms for minimizing decomposable functions and understanding their combinatorial structure.\u003C\/p\u003E\r\n\r\n\u003Cdiv\u003EThis talk is based on joint work with Huy Nguyen (Northeastern University) and Laszlo Vegh (London School of Economics).\u003C\/div\u003E\r\n\r\n\u003Cdiv\u003E\u0026nbsp;\u003C\/div\u003E\r\n\r\n\u003Cdiv\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nAlina Ene is an Assistant Professor in the Computer Science department at Boston University. Her research interests include the design and analysis of algorithms, the mathematical aspects of combinatorial optimization topics such as submodularity and graphs, and their applications to machine learning. Prior to joining BU, she was an Assistant Professor at the University of Warwick, a Faculty Fellow at the Alan Turing Institute for Data Science, and a postdoc in the Center for Computational Intractability at Princeton University. Alina obtained her PhD in Computer Science from the University of Illinois at Urbana-Champaign in 2013 under the supervision of Chandra Chekuri. She graduated with a BSE degree in Computer Science from Princeton University in 2008, with High Honors in Computer Science.\u003C\/div\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/cs-people.bu.edu\/aene\/\u0022\u003Ehttp:\/\/cs-people.bu.edu\/aene\/\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","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Recent progress on minimizing decomposable submodular functions (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-17 18:07:40","changed_gmt":"2017-04-13 21:15:04","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-10-17T12:00:00-04:00","event_time_end":"2016-10-17T13:00:00-04:00","event_time_end_last":"2016-10-17T13:00:00-04:00","gmt_time_start":"2016-10-17 16:00:00","gmt_time_end":"2016-10-17 17:00:00","gmt_time_end_last":"2016-10-17 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"},{"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":"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\u003Cbr \/\u003E\r\ndenton at cc dot gatech dot edu\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"568751":{"#nid":"568751","#data":{"type":"event","title":"ARC10","body":[{"value":"\u003Ch4 align=\u0022center\u0022\u003E\u003Cstrong\u003EARC10\u003C\/strong\u003E\u003C\/h4\u003E\r\n\r\n\u003Ch5 align=\u0022center\u0022\u003E\u003Cstrong\u003EA Special Event Celebrating the 10\u003Csup\u003Eth\u003C\/sup\u003E Anniversary of Georgia Tech\u0026#39;s\u003C\/strong\u003E\u003C\/h5\u003E\r\n\r\n\u003Ch5 align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms and Randomness Center\u003C\/strong\u003E\u003C\/h5\u003E\r\n\r\n\u003Ch5 align=\u0022center\u0022\u003E\u0026nbsp;\u003Cstrong\u003EMonday, October 24 in Klaus 1116\u003C\/strong\u003E\u003C\/h5\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EProgram Schedule:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E9:30\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Refreshments\u003C\/p\u003E\r\n\r\n\u003Cp\u003E10:00am: \u0026nbsp;\u003Cstrong\u003E ARC-IDEaS Distinguished Lecture by Jon Kleinberg\u003C\/strong\u003E \u0026ndash; Cornell University\u003Cbr \/\u003E\r\n\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;\u0026nbsp;\u003Ca href=\u0022http:\/\/arc.gatech.edu\/hg\/item\/560251\u0022\u003ETitle: \u003Cem\u003EHuman Decisions and Machine Predictions\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E11:00am: \u0026nbsp; Break\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E11:15am: \u0026nbsp; Josephine Yu - GT Math\u0026nbsp;\u003Cbr \/\u003E\r\n\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Title:\u0026nbsp;\u003Cem\u003ETropical Geometry in Economics\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E11:50am: \u0026nbsp; Mohit Singh - Microsoft\/GT ISyE\u0026nbsp;\u003Cbr \/\u003E\r\n\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Title:\u0026nbsp;\u003Cem\u003ENew Approaches for Constrained Subset Selection Problem\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;12:30\u0026nbsp;\u0026nbsp; Lunch in the Klaus Atrium\u003C\/p\u003E\r\n\r\n\u003Cp\u003E(Sponsored by Georgia Tech Colleges of Computing, Engineering, and\u0026nbsp;Sciences, and by Microsoft Research.)\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E* * * * *\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ESpeaker Abstracts:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EJon Kleinberg\u003C\/strong\u003E\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003E\u0026ndash; Cornell University\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u0026nbsp;\u003Cbr \/\u003E\r\n\u003Cem\u003EHuman Decisions and Machine Predictions\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nAn increasing number of domains are providing us with detailed trace data on human decisions, often made by experts with deep experience in the subject matter. This provides an opportunity to use machine-learning prediction algorithms to ask several families of questions --- not only about the extent to which algorithms can outperform expert-level human decision-making in specific domains, but also whether we can use algorithms to analyze the nature of the errors made by human experts, to predict which instances will be hardest for these experts, and to explore some of the ways in which prediction algorithms can serve as supplements to human decision-making in different applications.\u0026nbsp; In this talk, I\u0026#39;ll explore this theme by drawing on a line of recent projects; all are joint with Sendhil Mullainathan, and include collaborations with Ashton Anderson, Himabindu Lakkaraju, Jure Leskovec, Annie Liang, and Jens Ludwig.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nJon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on issues at the interface of networks and information, with an emphasis on the social and information networks that underpin the Web and other on-line media. He is a member of the National Academy of Sciences, the National Academy of Engineering, and the American Academy of Arts and Science; and he is the recipient of research fellowships from the MacArthur, Packard, Simons, and Sloan Foundations, as well as awards including the Nevanlinna Prize, the Harvey Prize, the Newell Award, and the ACM-Infosys Foundation Award in the Computing Sciences.\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E* * * * *\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EJosephine Yu\u003C\/strong\u003E\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003E\u0026ndash; Georgia Tech Math\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003ETropical Geometry in Economics\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nIn a recent and ongoing work, Baldwin and Klemperer explored a connection between tropical geometry and economics. They gave a sufficient condition for the existence of competitive equilibrium in product-mix auctions of indivisible goods. This result, which we call the Unimodularity Theorem, can also be traced back to the work of Danilov, Koshevoy, and Murota. We will introduce product-mix\u0026nbsp;auctions, prove the Unimodularity Theorem, and discuss integer programming formulations of this problem.\u0026nbsp; This is based on a joint work with Ngoc Mai Tran.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nJosephine Yu completed her Ph.D. in mathematics at UC Berkeley in 2007.\u0026nbsp; After postdoctoral positions at MIT and the Mathematical Sciences Research Institute in Berkeley, she joined the School of Mathematics at Georgia Tech in 2010.\u0026nbsp; Her research spans combinatorics, computational algebra, and polyhedral and algebraic geometry.\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E* * * * *\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EMohit Singh\u003C\/strong\u003E\u003Cstrong\u003E\u0026nbsp;\u003C\/strong\u003E\u0026ndash; Microsoft \/ Georgia Tech ISyE\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u0026nbsp;\u0026nbsp;\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003ENew Approaches for Constrained Subset Selection Problem\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nSelecting a diverse subset of items from a collection occurs as a fundamental problem in various applications including selecting representative documents from a corpus, selecting diverse geographical locations for sensor placement and designing most informative experiments. The problem is modeled by maximizing the entropy of the joint distribution of the selected items and, typically, has additional side constraints. We design approximation algorithms for the subset selection problem with additional partition constraints. Our algorithm relies on efficient polynomial optimization and reveals surprising connections to the problem of counting matchings via the theory of hyperbolic polynomials.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nMohit Singh is a researcher in the theory group at Microsoft Research, Redmond and will be joining ISyE, Georgia Tech in January 2017. His research interests include discrete optimization, approximation algorithms and convex optimization. Previously, he was an Assistant Professor at McGill University from 2010-2011 and a post-doctoral researcher at Microsoft Research, New England from 2008-2009. He obtained his Ph.D. from Tepper School of Business, Carnegie Mellon University and his doctoral thesis received the Tucker prize in 2009 given by the Mathematical Optimization Society. He has also received the best paper award for his work on the traveling salesman problem at the Annual Symposium on Foundations of Computer Science (FOCS) 2011.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"10th anniversary celebration of the Algorithms \u0026 Randomness Center featuring Jon Kleinberg (Cornell)"}],"uid":"27466","created_gmt":"2016-08-26 12:53:58","changed_gmt":"2017-04-13 21:14:57","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-10-24T10:30:00-04:00","event_time_end":"2016-10-24T14:30:00-04:00","event_time_end_last":"2016-10-24T14:30:00-04:00","gmt_time_start":"2016-10-24 14:30:00","gmt_time_end":"2016-10-24 18:30:00","gmt_time_end_last":"2016-10-24 18:30: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"},{"id":"168769","name":"ARC 10"},{"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":"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\u003Cbr \/\u003E\r\ndenton at cc dot gatech dot edu\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"581835":{"#nid":"581835","#data":{"type":"event","title":"Imlay Distinguished Lecture by Lenore Blum (CMU)","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EJohn P. Imlay Distinguished Lecture\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch2 align=\u0022center\u0022\u003E\u003Cstrong\u003ELenore Blum\u003C\/strong\u003E\u003C\/h2\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EThursday, October 27, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EHowey Physics Building Room L4 at 5pm\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch2 align=\u0022center\u0022\u003E\u003Cstrong\u003E\u003Cspan\u003EAlan Turing and the Other Theory of Computing\u003C\/span\u003E\u003C\/strong\u003E\u003C\/h2\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ESpeaker: \u0026nbsp;\u0026nbsp;\u003C\/strong\u003ELenore Blum\u003Cbr \/\u003E\r\n\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; Distinguished Career Professor of Computer Science\u003Cbr \/\u003E\r\n\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; Carnegie Mellon University (CMU)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EMost logicians and theoretical computer scientists are familiar with Alan Turing\u0026rsquo;s 1936 seminal paper setting the stage for the foundational (discrete) theory of computation. Most however remain unaware of Turing\u0026rsquo;s 1948 seminal paper which introduces the \u003Cem\u003Enotion of condition\u003C\/em\u003E, setting the stage for a natural theory of complexity for the \u0026ldquo;other theory of computation.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EComputational mathematics, the \u0026ldquo;other theory of computation,\u0026rdquo; emanates from the classical tradition of numerical analysis, equation solving and the continuous mathematics of calculus.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk will recognize Alan Turing\u0026rsquo;s work in the foundations of numerical computation (in particular, his 1948 paper \u0026ldquo;Rounding-Off Errors in Matrix Processes\u0026rdquo;), its influence in complexity theory today, and how it provides a unifying concept for the two major traditions of the Theory of Computation.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EJohn P. Imlay Distinguished Lecture\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThursday, October 27 at 5pm in Howey Physics L4\u003C\/p\u003E\r\n","format":"limited_html"}],"field_summary_sentence":[{"value":"CMU Distinguished Professor Lenore Blum speaking on Alan Turing and the Other Theory of Computing on Thursday, October 27 at 5pm in Howey Physics L4"}],"uid":"32895","created_gmt":"2016-09-28 16:21:45","changed_gmt":"2017-04-13 21:14:30","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-10-27T18:00:00-04:00","event_time_end":"2016-10-27T19:00:00-04:00","event_time_end_last":"2016-10-27T19:00:00-04:00","gmt_time_start":"2016-10-27 22:00:00","gmt_time_end":"2016-10-27 23:00:00","gmt_time_end_last":"2016-10-27 23: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":"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\u003EAlicia Richhart\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"582188":{"#nid":"582188","#data":{"type":"event","title":"ARC-IISP Distinguished Lecture by Manuel Blum (CMU)","body":[{"value":"Slides (pdf) from Manuel Blum\u0027s talk are available at:  \r\n\u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~vigoda\/Blum_Human_Computation.pdf\u0022\u003Ehttp:\/\/www.cc.gatech.edu\/~vigoda\/Blum_Human_Computation.pdf\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) and\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EInstitute for Information Security \u0026amp;\u0026nbsp;Privacy (IISP) present\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EARC-IISP\u0026nbsp;Distinguished Lecture\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch2 align=\u0022center\u0022\u003E\u003Cstrong\u003EManuel Blum\u003C\/strong\u003E\u003C\/h2\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EThursday, October 27, 11am at Klaus 1443\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch2 align=\u0022center\u0022\u003E\u003Cstrong\u003EHuman Computation with an Application to Passwords\u003C\/strong\u003E\u003C\/h2\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003Cbr \/\u003E\r\n\u003Cem\u003EHuman computation:\u003C\/em\u003E This talk presents a simple model of human computation based on well-known features of long and short term human memory. The intention of the model is to bring CS ideas and understanding to bear on the kinds of computations that humans can (and cannot) consciously perform in their heads.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThis work has applications to the study of problems that humans might want to solve in their heads, like how to solve crossword puzzles, play speed chess, and various cryptographic problems.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe running example in this talk will be password generation wherein humans - working entirely in their heads - transform website names into random-looking passwords that are provably hard to forge.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u0026mdash;\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cem\u003EApplication to passwords:\u003C\/em\u003E Nowadays, the best password advice suggests, for each website, to either select and memorize four random picturable words (XKCD), or choose a memorable sentence and use the first letter of every word for the password.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nOne problem with all such proposals is that they don\u0026#39;t indicate how to link website names to passwords. In effect, they would have you generate and memorize a special purpose password for every website. Little wonder that few people do this.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nWe recommend instead to use a humanly computable algorithm (schema) to transform website names into passwords on the fly. Schemas enable a human to have a (completely) different password for every website, to never have to write passwords down, and to be able to test password quality without giving any passwords away. They also enable us to analyze the Quality of Password Schemas mathematically.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nJoint work with Santosh Vempala.\u003Cbr \/\u003E\r\n\u0026nbsp;\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":"Turing Award Winner Manuel Blum speaking on Human Computation with an Application to Passwords on Thursday, October 27 at 11 a.m. in Klaus 1443 "}],"uid":"32895","created_gmt":"2016-10-05 23:23:20","changed_gmt":"2017-04-13 21:14:25","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-10-27T12:00:00-04:00","event_time_end":"2016-10-27T13:00:00-04:00","event_time_end_last":"2016-10-27T13:00:00-04:00","gmt_time_start":"2016-10-27 16:00:00","gmt_time_end":"2016-10-27 17:00:00","gmt_time_end_last":"2016-10-27 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":"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\u003EElizabeth Ndongi\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"582448":{"#nid":"582448","#data":{"type":"event","title":"ARC Colloquium: David Witmer - CMU","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\u003EDavid Witmer - CMU\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, December 5, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nUsing the sum of squares hierarchy to refute random CSPs\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003Cbr \/\u003E\r\nConsider a random constraint satisfaction problem (CSP) over $n$ variables with $m = \u0026Delta; n$ constraints, each being a predicate $P$ applied to $k$ random literals. When \u0026Delta; \u003E\u003E 1$, the instance will be unsatisfiable with high probability, and the natural associated algorithmic task is to find a refutation --- i.e., a certificate of unsatisfiability.\u0026nbsp; Understanding the density required for average-case refutation is important in various areas of complexity including cryptography, proof complexity, and learning theory.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, we discuss refutation of random CSPs using the sum of squares (SOS) hierarchy.\u0026nbsp; The SOS hierarchy is a sequence of semidefinite relaxations parameterized by a value called the degree.\u0026nbsp; As the degree increases, the relaxation becomes tighter, but the size of its description increases.\u0026nbsp; We give an overview of recent work proving that the SOS degree required to refute a random instance of CSP$(P)$ is essentially determined by the smallest $t$ for which $P$ does not support a $t$-wise uniform distribution over satisfying assignments.\u0026nbsp; Specifically, if $P$ fails to support a $t$-wise uniform distribution, our work together with recent work of Raghavendra, Rao, and Schramm shows that degree-$\\frac{n}{\\Delta^{2\/(t-2)}}$ SOS can refute random instances of CSP$(P)$.\u0026nbsp; Furthermore, this result is tight up to polylogarithmic factors.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis talk is based on joint work with Sarah R. Allen, Pravesh Kothari, Ryuhei Mori, and Ryan O\u0026rsquo;Donnell.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/www.cs.cmu.edu\/~dwitmer\/\u0022\u003Ehttp:\/\/www.cs.cmu.edu\/~dwitmer\/\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESeminar webpage: \u003Ca href=\u0022http:\/\/arc.gatech.edu\/hg\/item\/582448\u0022\u003Ehttp:\/\/arc.gatech.edu\/hg\/item\/582448\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","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Using the sum of squares hierarchy to refute random CSPs (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-10-12 17:27:11","changed_gmt":"2017-04-13 21:14:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-12-05T11:00:00-05:00","event_time_end":"2016-12-05T12:00:00-05:00","event_time_end_last":"2016-12-05T12:00:00-05:00","gmt_time_start":"2016-12-05 16:00:00","gmt_time_end":"2016-12-05 17:00:00","gmt_time_end_last":"2016-12-05 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"id":"50877","name":"School of Computational Science and Engineering"}],"categories":[],"keywords":[{"id":"92341","name":"Algorithms 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\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"582558":{"#nid":"582558","#data":{"type":"event","title":"ARC-ML Colloquium: Yin-Tat Lee - University of Washington","body":[{"value":"\u003Cp\u003EPlease note that this talk is held at noon on a Wednesday.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Algorithms \u0026amp; Randomness Center (ARC) and\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Machine Learning Group present\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; ARC - ML Colloquium\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;\u003Ca href=\u0022http:\/\/yintat.com\u0022\u003EYin-Tat Lee\u003C\/a\u003E \u0026ndash;\u003C\/strong\u003E \u003Cstrong\u003EUniversity of Washington\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Wednesday, November 9\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Klaus 1116 East \u0026ndash; Noon\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003ETitle: \u0026nbsp; \u0026nbsp;\u003C\/strong\u003EGeodesic Walks\u003C\/h3\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nWe introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes in R^n specified by m inequalities. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold. The resulting sampling algorithm for polytopes mixes in O*(mn^{3\/4}) steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Geodesic Walks (Klaus 1116E at noon)"}],"uid":"32895","created_gmt":"2016-10-14 01:59:13","changed_gmt":"2017-04-13 21:14:18","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-11-09T12:00:00-05:00","event_time_end":"2016-11-09T13:00:00-05:00","event_time_end_last":"2016-11-09T13:00:00-05:00","gmt_time_start":"2016-11-09 17:00:00","gmt_time_end":"2016-11-09 18:00:00","gmt_time_end_last":"2016-11-09 18: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":"9167","name":"machine learning"},{"id":"172450","name":"Randomized Algorithms"},{"id":"4336","name":"geometry"}],"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":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}