{"611722":{"#nid":"611722","#data":{"type":"event","title":"ARC Colloquium: Venkat Guruswami (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\u003EVenkat Guruswami\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, December 3, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116E - 11:00 am\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\u003EThe polymorphic gateway between structure and algorithms: Beyond\u0026nbsp;CSPs\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems (CSPs), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are\u0026nbsp;non-trivial\u0026nbsp;local\u0026nbsp;operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete.\u0026nbsp;Inspired and emboldened by this, one might speculate a broader polymorphic principle: if there are interesting ways to combine solutions to get more solutions, then the problem ought to be tractable (with context dependent interpretations of\u0026nbsp;\u0026quot;interesting\u0026quot; and \u0026quot;tractable\u0026rdquo;).\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBeginning with some background on the polymorphic approach to understanding the complexity of constraint satisfaction, the talk will discuss some extensions\u0026nbsp;beyond CSPs where the polymorphic principle seems promising (yet far from understood). Specifically, we will discuss promise CSPs where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring and discrepancy minimization), and the potential and challenges in applying the polymorphic framework to them. Another interesting direction is fine-grained complexity, where partial polymorphisms govern the runtime of fast exponential-time algorithms. Our inquiries into these directions also reveal some interesting connections to optimization, such as algorithms to solve LPs over different rings (like integers adjoined with sqrt{2}), and a random-walk based algorithm interpolating between 0-1 and linear programming, generalizing\u0026nbsp;Sch\u0026ouml;ning\u0026#39;s\u0026nbsp;famous (4\/3)^n time algorithm for 3-SAT.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased\u0026nbsp;on a body of work with Joshua Brakensiek.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cs.cmu.edu\/~venkatg\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The polymorphic gateway between structure and algorithms: Beyond CSPs - Klaus 1116E at 11 am"}],"uid":"27544","created_gmt":"2018-09-20 14:58:53","changed_gmt":"2018-11-19 20:36:45","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-12-03T11:00:00-05:00","event_time_end":"2018-12-03T12:00:00-05:00","event_time_end_last":"2018-12-03T12:00:00-05:00","gmt_time_start":"2018-12-03 16:00:00","gmt_time_end":"2018-12-03 17:00:00","gmt_time_end_last":"2018-12-03 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"610220":{"#nid":"610220","#data":{"type":"event","title":"ARC-TRIAD Colloquium: Michael Mitzenmacher (Harvard)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EARC-TRIAD Colloquium\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMichael Mitzenmacher\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 26, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EBloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; I will go over some of my past and present work on hashing-based data structures.\u0026nbsp; After presenting some background on Bloom filters and cuckoo hashing, we will describe cuckoo filters, an efficient data structure for approximate set membership that improves on the well-known Bloom filter. We then discuss recent work on how to make cuckoo filters adaptive in response to false positives, which can be important for many practical problems.\u0026nbsp; Finally, I will present some very recent work on how to possibly improve Bloom filters and related data structures using machine learning techniques.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.eecs.harvard.edu\/~michaelm\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters - Klaus 1116E at 11 am"}],"uid":"27544","created_gmt":"2018-08-23 12:03:55","changed_gmt":"2018-11-02 18:00:23","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-11-26T11:00:00-05:00","event_time_end":"2018-11-26T12:00:00-05:00","event_time_end_last":"2018-11-26T12:00:00-05:00","gmt_time_start":"2018-11-26 16:00:00","gmt_time_end":"2018-11-26 17:00:00","gmt_time_end_last":"2018-11-26 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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"611936":{"#nid":"611936","#data":{"type":"event","title":"ARC Colloquium: Sampath Kannan (UPenn)","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\u003ESampath Kannan\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 29, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EFairness in Algorithmic Decision Making\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E1) Treating individuals fairly is not in conflict with long-term scientific learning goals if the population is sufficiently diverse.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E2) When there is a pipeline of decisions, end-to-end fairness is impossible to achieve even in a very simple model.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E3) Exploiting the knowledge acquired by others can unfairly advantage the free rider.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThese papers are joint work with a number of co-authors:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EChristopher Jung, Neil Lutz, Jamie Morgenstern, Aaron Roth, Bo Waggoner, Steven Wu, and Juba Ziani\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.cis.upenn.edu\/~kannan\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":" Fairness in Algorithmic Decision Making - Klaus 1116 East at 11 am"}],"uid":"27544","created_gmt":"2018-09-25 18:22:44","changed_gmt":"2018-10-09 12:12:33","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-10-29T12:00:00-04:00","event_time_end":"2018-10-29T13:00:00-04:00","event_time_end_last":"2018-10-29T13:00:00-04:00","gmt_time_start":"2018-10-29 16:00:00","gmt_time_end":"2018-10-29 17:00:00","gmt_time_end_last":"2018-10-29 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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"607600":{"#nid":"607600","#data":{"type":"event","title":"ARC-TRIAD Colloquium: Mary Wootters (Stanford)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EARC-TRIAD Colloquium\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMary Wootters\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 1, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMiRC Pettit 102A\u0026amp;B - 11:00 am\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\u003EImproved Decoding of Folded Reed-Solomon and Multiplicity Codes\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; List-decoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacity-achieving, efficiently list-decodable codes.\u0026nbsp; Folded Reed-Solomon Codes (Guruswami-Rudra 2008) and Multiplicity codes (Guruswami-Wang 2011, Kopparty 2012) are two such constructions.\u0026nbsp; However, previous analysis of these codes could not guarantee optimal parameters.\u0026nbsp; In particular, the \u0026ldquo;list-size\u0026rdquo; of these codes was only shown to be polynomial, while ideally it would be constant.\u0026nbsp; Thus, over the past decade or so, there have been several modifications of these codes aimed at reducing the list size to constant.\u0026nbsp; In this work, we show that in fact the list-sizes were constant all along, with no modifications required!\u0026nbsp; Further, we use our result for univariate multiplicity codes to establish improved local list-decoding results for multivariate multiplicity codes.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, I\u0026rsquo;ll define all the terms in the paragraph above (in particular, no prior knowledge of error correcting codes is necessary!), and sketch the proofs of the results mentioned above.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with Swastik Kopparty, Noga Ron-Zewi, and Shubhangi Saraf.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/sites.google.com\/site\/marywootters\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Improved Decoding of Folded Reed-Solomon and Multiplicity Codes - MiRC Pettit 102 A\u0026B at 11 am"}],"uid":"27544","created_gmt":"2018-07-10 14:31:26","changed_gmt":"2018-10-01 13:10:14","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-10-01T12:00:00-04:00","event_time_end":"2018-10-01T13:00:00-04:00","event_time_end_last":"2018-10-01T13:00:00-04:00","gmt_time_start":"2018-10-01 16:00:00","gmt_time_end":"2018-10-01 17:00:00","gmt_time_end_last":"2018-10-01 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":"1792","name":"Arts and Performance"},{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"607350":{"#nid":"607350","#data":{"type":"event","title":"ARC-TRIAD Colloquium: Leslie Valiant (Harvard)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EARC-TRIAD Colloquium\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003ELeslie Valiant\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 22, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026amp; West\u0026nbsp; \u0026ndash; 11:00 am\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\u003EWhere Computer Science Meets Neuroscience\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; For some problems in science there are several plausible theories and it remains to experimenters to determine which of them, if any, are valid. There exist other problems for which, in contrast, no known theory is widely accepted as plausible. Currently computational neuroscience is a field full of opportunity that offers several fundamental problems of the latter kind. We shall discuss one of these problems: Over a lifetime the brain performs hundreds of thousands of individual cognitive acts, of a variety of kinds, including the formation of new associations. Each such act depends on past experience, and, in turn, can have long lasting effects on future behavior. It is difficult to reconcile such large scale capabilities, including fast reaction times on new inputs when using knowledge acquired at various earlier times, with the known resource constraints on cortex, such as low connectivity and low average synaptic strength. Here we shall describe an approach to this fundamental problem that attempts to explain these phenomena in terms of concrete algorithms for a model of computation that is faithful to the most basic quantitative resources.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.seas.harvard.edu\/directory\/valiant\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Where Computer Science Meets Neuroscience - Klaus 1116 E \u0026 W at 11 am"}],"uid":"27544","created_gmt":"2018-06-27 19:15:09","changed_gmt":"2018-10-01 13:07:01","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-10-22T12:00:00-04:00","event_time_end":"2018-10-22T13:00:00-04:00","event_time_end_last":"2018-10-22T13:00:00-04:00","gmt_time_start":"2018-10-22 16:00:00","gmt_time_end":"2018-10-22 17:00:00","gmt_time_end_last":"2018-10-22 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"611934":{"#nid":"611934","#data":{"type":"event","title":"ARC Colloquium: Will Perkins (UIC)","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\u003EWill Perkins\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 5, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EAlgorithmic Pirogov-Sinai theory\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; We develop efficient algorithms to approximate the partition function and sample from the hard-core and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In contrast, the Glauber dynamics are known to take exponential time to mix in this regime.\u0026nbsp; Our algorithms are based on the cluster expansion and Pirogov-Sinai theory, classical tools from statistical physics for understanding phase transitions, as well as Barvinok\u0026#39;s approach to polynomial approximation.\u0026nbsp; Joint work with Tyler Helmuth and Guus Regts.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/willperkins.org\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Algorithmic Pirogov-Sinai theory - Klaus 1116 East at 11 am"}],"uid":"27544","created_gmt":"2018-09-25 18:10:05","changed_gmt":"2018-09-25 18:10:05","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-11-05T11:00:00-05:00","event_time_end":"2018-11-05T12:00:00-05:00","event_time_end_last":"2018-11-05T12:00:00-05:00","gmt_time_start":"2018-11-05 16:00:00","gmt_time_end":"2018-11-05 17:00:00","gmt_time_end_last":"2018-11-05 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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"607596":{"#nid":"607596","#data":{"type":"event","title":"ARC Colloquium: Tselil Schramm (Harvard\/MIT)","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\u003ETselil Schramm\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 24, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMiRC Pettit 102 A\u0026amp;B\u0026nbsp; \u0026ndash; 11:00 am\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(Nearly) Efficient Algorithms for the\u0026nbsp;Graph\u0026nbsp;Matching\u0026nbsp;Problem in Correlated Random\u0026nbsp;Graphs\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; The\u0026nbsp;Graph\u0026nbsp;Matching\u0026nbsp;problem is a robust version of the\u0026nbsp;Graph\u0026nbsp;Isomorphism problem: given two not-necessarily-isomorphic\u0026nbsp;graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular average-case variant; we deviate from the common heuristic strategy and give the first quasi-polynomial time algorithm, where previously only sub-exponential time algorithms were known.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased on joint work with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/tselilschramm.org\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"(Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs - MiRC Pettit 102 A\u0026B at 11 am"}],"uid":"27544","created_gmt":"2018-07-10 14:01:41","changed_gmt":"2018-09-17 11:50:28","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-09-24T12:00:00-04:00","event_time_end":"2018-09-24T13:00:00-04:00","event_time_end_last":"2018-09-24T13:00:00-04:00","gmt_time_start":"2018-09-24 16:00:00","gmt_time_end":"2018-09-24 17:00:00","gmt_time_end_last":"2018-09-24 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"604923":{"#nid":"604923","#data":{"type":"event","title":"ARC Colloquium: Lap Chi Lau (Waterloo)","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\u003ELap Chi Lau\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 15, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EThe Paulsen problem, continuous operator scaling, and smoothed analysis\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; The\u0026nbsp;Paulsen\u0026nbsp;problem is a basic open problem in operator theory.\u0026nbsp; We define\u0026nbsp;a continuous version of the operator scaling algorithm to solve this problem.\u0026nbsp; A key step is to show that the continuous operator scaling algorithm converges faster in a perturbed input. To this end, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm.\u0026nbsp; The talk will be self-contained.\u0026nbsp; \u0026nbsp;Joint work with Tsz Chiu Kwok, Yin Tat Lee, and Akshay Ramachandran.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/cs.uwaterloo.ca\/~lapchi\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Paulsen problem, continuous operator scaling, and smoothed analysis - Klaus 1116E at 11 am"}],"uid":"27544","created_gmt":"2018-04-10 19:11:27","changed_gmt":"2018-09-14 13:26:48","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-10-15T12:00:00-04:00","event_time_end":"2018-10-15T13:00:00-04:00","event_time_end_last":"2018-10-15T13:00:00-04:00","gmt_time_start":"2018-10-15 16:00:00","gmt_time_end":"2018-10-15 17:00:00","gmt_time_end_last":"2018-10-15 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":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"609429":{"#nid":"609429","#data":{"type":"event","title":"ARC Colloquium: Anand Louis (Indian Inst. of Science)","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\u003EAnand Louis (Indian Inst. of Science)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 10, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EOn the complexity of clustering problems\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of real-world data sets that allow efficient clustering has lead to the notion of the perturbation resilience. In the first part of the talk, I\u0026#39;ll describe an algorithm to recover the optimal k-means clustering in perturbation resilient instances.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn some cases, clustering with the k-means objective may result in a few clusters of very large cost and many clusters of small cost. This can be undesirable when we have a budget constraint on the cost of each cluster. Motivated by this, we study the \u0026quot;min-max k-means\u0026quot; clustering objective. In the second part of the talk, I\u0026#39;ll show approximation algorithms for the min-max k-means problem.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EBased on joint works with Amit Deshpande and Apoorv Vikram Singh.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/drona.csa.iisc.ac.in\/~anand\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"On the complexity of clustering problems - Klaus 1116E at 11 am"}],"uid":"27544","created_gmt":"2018-08-08 14:00:43","changed_gmt":"2018-08-31 16:39:56","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-09-10T12:00:00-04:00","event_time_end":"2018-09-10T13:00:00-04:00","event_time_end_last":"2018-09-10T13:00:00-04:00","gmt_time_start":"2018-09-10 16:00:00","gmt_time_end":"2018-09-10 17:00:00","gmt_time_end_last":"2018-09-10 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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"604927":{"#nid":"604927","#data":{"type":"event","title":"ARC Colloquium:  Nima Anari (Stanford)","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\u003ENima Anari\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 30, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; Noon\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\n\u003Cstrong\u003ETitle:\u0026nbsp; \u003C\/strong\u003EEntropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; We give a deterministic 2^O(rank) approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. Based on a lower bound of Azar et al., this is almost the best possible result assuming oracle access to independent sets of matroids.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThere are two main ingredients in our result: For the first ingredient, we build upon recent results of Huh et al. and Adiprasito et al. on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. We expect that several new applications in approximation algorithms will be derived from this connection in future. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant. For the second ingredient, we use a general framework for approximate counting in discrete problems, based on convex optimization and sub-additivity of the entropy. For matroids, we prove that an approximate super-additivity of the entropy holds, yielding an approximation algorithm, by relying on log-concavity of the corresponding polynomials.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with Shayan Oveis Gharan and Cynthia Vinzant.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/nimaanari.com\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids - Klaus 1116E at 11 am"}],"uid":"27544","created_gmt":"2018-04-10 19:32:13","changed_gmt":"2018-04-24 18:15:29","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-04-30T13:00:00-04:00","event_time_end":"2018-04-30T14:00:00-04:00","event_time_end_last":"2018-04-30T14:00:00-04:00","gmt_time_start":"2018-04-30 17:00:00","gmt_time_end":"2018-04-30 18:00:00","gmt_time_end_last":"2018-04-30 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"601434":{"#nid":"601434","#data":{"type":"event","title":"ARC Colloquium:  Alexandre Stauffer (Bath)","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\u003EAlexandre Stauffer\u0026nbsp;(Bath)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, April 23, 2018\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:\u003C\/strong\u003E\u0026nbsp; Competition in randomly growing processes\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003EWe consider random growth processes that compete for space over time.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is by now a classical topic in probability theory. The usual situation is that when the two processes have different speeds of growth, then one of the processes wins against the other.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIt is quite rare to find natural models where both processes coexist forever.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk I will discuss a random growth model, which we introduced as a tool to studying a famous model of dendritic growth from physics.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis growth model can also be regarded as a model for blocking the spread of fake news in a network.\u0026nbsp;\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe will discuss the behavior of this processes, its phase transition and the occurrence of coexistence.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is based on joint works with Elisabetta Candellero (Warwick) and Vladas Sidoravicius (NYU Shanghai).\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/sites.google.com\/site\/alexandrestauffer\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\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":"Competition in randomly growing processes - Klaus 1116E at 11am"}],"uid":"32895","created_gmt":"2018-01-26 19:30:59","changed_gmt":"2018-04-16 19:19:34","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-04-23T12:00:00-04:00","event_time_end":"2018-04-23T13:00:00-04:00","event_time_end_last":"2018-04-23T13:00:00-04:00","gmt_time_start":"2018-04-23 16:00:00","gmt_time_end":"2018-04-23 17:00:00","gmt_time_end_last":"2018-04-23 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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"603173":{"#nid":"603173","#data":{"type":"event","title":"ARC Colloquium:  Yin Tat Lee (UW)","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\u003EYin Tat Lee\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EFriday, March 16, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMiRC Pettit Rm 102A\u0026amp;B \u0026ndash; 11:00 am\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\u003El_p regression beyond self-concordance\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; We consider the problem of linear regression where the l_2 norm loss (i.e., the usual least squares loss) is replaced by the l_p norm. We show how to solve such problems up to machine precision in O*(n^|1\/2\u0026minus;1\/p|) (dense) matrix-vector products and O*(1) matrix inversions, or alternatively in O*(n^|1\/2\u0026minus;1\/p|) calls to a (sparse) linear system solver. This improves the state of the art for any p not in {1,2,inf}. Furthermore we also propose a randomized algorithm solving such problems in input sparsity time, i.e., O*(Z+poly(d)) where Z is the size of the input and d is the number of variables. Such a result was only known for p=2. Finally we prove that these results lie outside the scope of the Nesterov-Nemirovski\u0026#39;s theory of interior point methods by showing that any symmetric self-concordant barrier on the l_p unit ball has self-concordance parameter \u0026Omega;~(n).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with S\u0026eacute;bastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/yintat.com\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"l_p regression beyond self-concordance - MiRC Pettit Rm 102A\u0026B at 11:00am"}],"uid":"27544","created_gmt":"2018-03-02 13:19:43","changed_gmt":"2018-03-02 13:22:39","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-03-16T12:00:00-04:00","event_time_end":"2018-03-16T13:00:00-04:00","event_time_end_last":"2018-03-16T13:00:00-04:00","gmt_time_start":"2018-03-16 16:00:00","gmt_time_end":"2018-03-16 17:00:00","gmt_time_end_last":"2018-03-16 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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"601435":{"#nid":"601435","#data":{"type":"event","title":"ARC-TRIAD Colloquium:  Piotr Indyk (MIT)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) and TRIAD\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EPiotr Indyk\u0026nbsp;(MIT)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 5, 2018\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:\u003C\/strong\u003E\u0026nbsp; \u0026nbsp;\u0026quot;Below P vs. NP: Conditional Quadratic-Time Hardness for Big Data Problems\u0026quot;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E \u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe theory of NP-hardness has been very successful in identifying problems that are unlikely to have general purpose polynomial time algorithms. However, many other important problems do have polynomial time algorithms, but large exponents in their time bounds can make them run for days, weeks or more. For example, quadratic time algorithms, although practical on moderately sized inputs, can become inefficient on problems that involve gigabytes or more of data. Although for many problems no subquadratic time algorithms are known, evidence of quadratic-time hardness has remained elusive.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, I will give an overview of recent research that aims to remedy this situation. In particular, I will describe hardness results for problems in string processing (e.g., edit distance computation or regular expression matching) and machine learning (e.g., support vector machines or batch gradient computation in neural networks). All of them have polynomial time algorithms, but despite an extensive amount of research, no near-linear time algorithms have been found for many variants of these problems. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also describe how this framework has led to the development of new algorithms.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/people.csail.mit.edu\/indyk\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\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":"\u0022Below P vs. NP: Conditional Quadratic-Time Hardness for Big Data Problems\u0022 - Klaus 1116E at 11am"}],"uid":"32895","created_gmt":"2018-01-26 19:32:00","changed_gmt":"2018-02-27 14:01:59","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-03-05T11:00:00-05:00","event_time_end":"2018-03-05T12:00:00-05:00","event_time_end_last":"2018-03-05T12:00:00-05:00","gmt_time_start":"2018-03-05 16:00:00","gmt_time_end":"2018-03-05 17:00:00","gmt_time_end_last":"2018-03-05 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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"602428":{"#nid":"602428","#data":{"type":"event","title":"ARC Colloquium: Sanjeev Arora (Princeton\/IAS)","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\u003ESanjeev Arora\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EPrinceton University and Institute for Advanced Study\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EFriday, February 23, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 2447 (classroom) at 11:00 am\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\u003EToward theoretical understanding of deep learning\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; This talk will be a survey of ongoing efforts to develop better theoretical understanding of deep learning, from expressiveness to optimization to generalization theory.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.cs.princeton.edu\/~arora\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Toward theoretical understanding of deep learning - Klaus 2447 (classroom) at 11am"}],"uid":"32895","created_gmt":"2018-02-15 17:53:57","changed_gmt":"2018-02-20 14:16:15","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-23T11:00:00-05:00","event_time_end":"2018-02-23T12:00:00-05:00","event_time_end_last":"2018-02-23T12:00:00-05:00","gmt_time_start":"2018-02-23 16:00:00","gmt_time_end":"2018-02-23 17:00:00","gmt_time_end_last":"2018-02-23 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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"601432":{"#nid":"601432","#data":{"type":"event","title":"ARC Colloquium:  Xiaorui Sun (Microsoft)","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\u003EXiaorui Sun\u0026nbsp;(Microsoft Research)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, March 12, 2018\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:\u003C\/strong\u003E\u0026nbsp;\u0026nbsp; The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E \u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWe study the edge query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n^{1+o(1)} queries, improving on the previous best bound of O~(n^{5\/4}). Since the problem is known to require \\Omega(n) queries, our algorithm is optimal up to a subpolynomial factor.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EWhile trying to extend a known connection to distribution testing, discovered by Fischer and Matsliah (SICOMP 2008), one encounters a natural obstacle presented by sampling lower bounds such as the $\\Omega(n^{2\/3})$-sample lower bound for distribution closeness testing (Valiant, SICOMP 2011). In the context of graph isomorphism testing, these bounds lead to an $n^{1+\\Omega(1)}$ barrier for Fischer and Matsliah\u0026#39;s approach. We circumvent these limitations by exploiting a geometric representation of the connectivity of vertices. An approximate representation of similarities between vertices can be learned with a near-linear number of queries and allows relaxed versions of sampling and distribution testing problems to be solved more efficiently.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EJoint work with Krzysztof Onak\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cs.columbia.edu\/~xiaoruisun\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\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":" The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds- Klaus 1116E at 11am"}],"uid":"32895","created_gmt":"2018-01-26 19:29:25","changed_gmt":"2018-02-16 21:10:52","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-03-12T12:00:00-04:00","event_time_end":"2018-03-12T13:00:00-04:00","event_time_end_last":"2018-03-12T13:00:00-04:00","gmt_time_start":"2018-03-12 16:00:00","gmt_time_end":"2018-03-12 17:00:00","gmt_time_end_last":"2018-03-12 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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"602340":{"#nid":"602340","#data":{"type":"event","title":"ARC Colloquium:  Vivek Madan (UIUC)","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\u003EVivek Madan(UIUC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 19, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EApproximating Multicut and the Demand graph\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; The Multicut problem is a generalization of the classical $s-t$ cut problem to multiple pairs. Given an edge-weighted directed or undirected supply graph G=(V,E), and k source-sink pairs (s1,t1),\\dots,(sk,tk), the goal is to remove a minimum weight subset of edges in G such that all the given (si,ti) pairs are disconnected. Over the past 30 years, Multicut has attracted significant attention in approximation algorithms, and a variety of results have been obtained for general and special classes of supply graphs. Motivated by new applications, I study Multicut with a focus on the demand graph (graph with an edge set {(si,ti) \\mid i \\in [k]}). We obtain several new approximability and inapproximability results based on a labeling viewpoint of the problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E1.\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Approximation algorithms: We present a unified 2-approximation algorithm for undirected multicut problem for tK2-free demand graphs when t is a fixed constant. For directed multiway cut we significantly simplify the 2-approximation algorithm of Naor and Zosin from twenty years ago; our rounding strategy yields a constant factor for much more general classes of demand graphs. For the problem of linear-k-cut (a special case of directed multicut which motivated this work), we show some initial results and prove a tight \\sqrt{2}-approximation algorithm when k=3.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E2.\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Hardness of approximation: We prove that for a class of demand graphs, undirected multicut admits a constant factor approximation algorithm iff the class is tK2-free for some constant t. For directed multicut, we prove that assuming the Unique Games Conjecture (UGC), hardness of approximation matches the flow-cut gap for any fixed bi-partite demand graph. As a consequence, we prove that for any fixed k \\ge 2, there is no (k-eps) approximation algorithm for Multicut with k pairs, assuming UGC.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/vmadan2.web.engr.illinois.edu\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Approximating Multicut and the Demand Graph - Klaus 1116 East at 11:00am"}],"uid":"27544","created_gmt":"2018-02-14 12:53:08","changed_gmt":"2018-02-14 20:37:21","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-19T11:00:00-05:00","event_time_end":"2018-02-19T12:00:00-05:00","event_time_end_last":"2018-02-19T12:00:00-05:00","gmt_time_start":"2018-02-19 16:00:00","gmt_time_end":"2018-02-19 17:00:00","gmt_time_end_last":"2018-02-19 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":[],"invited_audience":[{"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":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"601408":{"#nid":"601408","#data":{"type":"event","title":"ARC Colloquium:  Greg Bodwin (MIT)","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\u003EGreg Bodwin\u0026nbsp;(MIT)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EFriday, February 9, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003ESkiles 005 - 1pm\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ENote the non-standard date\/time\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp; \u0026nbsp; The Distance Oracle Hierarchy\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E \u0026nbsp; A lot of well-studied problems in CS Theory are about making \u0026ldquo;sketches\u0026rdquo; of graphs that occupy much less space than the graph itself, but where the shortest path distances of the graph can still be approximately recovered from the sketch. For example, in the literature on Spanners, we seek a sparse subgraph whose distance metric approximates that of the original graph. In Emulator literature, we relax the requirement that the approximating graph is a subgraph. Most generally, in Distance Oracles, the sketch can be an arbitrary data structure, so long as it can approximately answer queries about the pairwise distance between nodes in the original graph.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EResearch on these objects typically focuses on optimizing the worst-case tradeoff between the quality of the approximation and the amount of space that the sketch occupies. In this talk, we will survey a recent leap in understanding about this tradeoff, overturning the conventional wisdom on the problem. Specifically, the tradeoff is not smooth, but rather it follows a new discrete hierarchy in which the quality of the approximation that can be obtained jumps considerably at certain predictable size thresholds. The proof is graph-theoretic and relies on building large families of graphs with large discrepancies in their metrics.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/sites.google.com\/site\/gregbodwin\/\u0022\u003ESpeaker\u0026#39;s webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\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":"The Distance Oracle Hierarchy - Skiles 005 at 1pm "}],"uid":"32895","created_gmt":"2018-01-26 16:58:52","changed_gmt":"2018-01-30 19:37:55","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-09T13:00:00-05:00","event_time_end":"2018-02-09T14:00:00-05:00","event_time_end_last":"2018-02-09T14:00:00-05:00","gmt_time_start":"2018-02-09 18:00:00","gmt_time_end":"2018-02-09 19:00:00","gmt_time_end_last":"2018-02-09 19: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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"601198":{"#nid":"601198","#data":{"type":"event","title":"ARC Colloquium: Aaron Schild (Berkeley)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAaron Schild (Berkeley)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 12, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026ndash; 11:00 am\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\u003EAn almost-linear time algorithm for uniform random spanning tree generation\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; We give an $m^{1+o(1)}\\beta^{o(1)}$-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio $\\beta$. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EOur starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex $v$ to the boundary of a set of vertices assigned to $v$ called a \u0026quot;shortcutter.\u0026quot; We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter $S$ to random walk steps in the Schur complement obtained by eliminating all vertices in $S$ that are not assigned to it.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/people.eecs.berkeley.edu\/~aschild\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"An almost-linear time algorithm for uniform random spanning tree generation - Klaus 1116 East at 11am"}],"uid":"27544","created_gmt":"2018-01-23 15:53:40","changed_gmt":"2018-01-29 13:36:28","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-12T11:00:00-05:00","event_time_end":"2018-02-12T12:00:00-05:00","event_time_end_last":"2018-02-12T12:00:00-05:00","gmt_time_start":"2018-02-12 16:00:00","gmt_time_end":"2018-02-12 17:00:00","gmt_time_end_last":"2018-02-12 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":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"601407":{"#nid":"601407","#data":{"type":"event","title":"ARC Colloquium: Di Wang (Berkeley\/GaTech)","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\u003EDi Wang\u0026nbsp;(UC Berkeley\/Georgia Tech)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 5, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East\u0026nbsp;- 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp; \u0026nbsp;Capacity Releasing Diffusion for Speed and Locality\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E \u0026nbsp; Diffusion and related random walk procedures on graphs are of central importance in many areas of machine learning, data analysis, and algorithm design. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread mass \u0026ldquo;too aggressively,\u0026rdquo; thereby failing to find the \u0026ldquo;right\u0026rdquo; clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both faster and stays more local than the classical probability mass diffusion.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe CRD Process follows a carefully-constructed push-relabel rule, using techniques that are well-known from flow-based graph algorithms. While \ufb02ow and probability mass diffusion (or more generally, spectral methods) have a long history of competing to provide good graph decomposition, local methods are predominantly based on diffusion. Our CRD Process is the \ufb01rst primarily \ufb02ow-based local method for locating low conductance cuts, and it has exhibited improved theoretical and empirical behavior over classical di\ufb00usion methods, e.g. PageRank.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\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":"Capacity Releasing Diffusion for Speed and Locality - Klaus 1116E at 11am"}],"uid":"32895","created_gmt":"2018-01-26 16:49:55","changed_gmt":"2018-01-26 19:37:42","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-05T11:00:00-05:00","event_time_end":"2018-02-05T12:00:00-05:00","event_time_end_last":"2018-02-05T12:00:00-05:00","gmt_time_start":"2018-02-05 16:00:00","gmt_time_end":"2018-02-05 17:00:00","gmt_time_end_last":"2018-02-05 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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"600861":{"#nid":"600861","#data":{"type":"event","title":"ARC-TRIAD Seminar - Yan Shuo Tan (Michigan)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EARC-TRIAD\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EYan Shuo Tan (Michigan)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, January 22, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EPettit Microelectonics Bldg. \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EPettit Rm 102A  -  2:00 pm\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\u003EEfficient algorithms for phase retrieval in high dimensions\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; Mathematical phase retrieval is the problem of solving systems of rank-1 quadratic equations. Over the last few years, there has been much interest in constructing algorithms with provable guarantees. Both theoretically and empirically, the most successful approaches have involved direct optimization of non-convex loss functions. In the first half of this talk, we will discuss how SGD for one of these loss functions provably results in (rapid) linear convergence with high probability. In the second half of the talk, we will discuss a semidefinite programming algorithm that simultaneously makes use of a sparsity prior on the solution vector, while overcoming possible model misspecification.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www-personal.umich.edu\/~yanshuo\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Efficient algorithms for phase retrieval in high dimensions"}],"uid":"27544","created_gmt":"2018-01-16 17:22:12","changed_gmt":"2018-01-19 15:33:31","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-01-22T14:00:00-05:00","event_time_end":"2018-01-22T15:00:00-05:00","event_time_end_last":"2018-01-22T15:00:00-05:00","gmt_time_start":"2018-01-22 19:00:00","gmt_time_end":"2018-01-22 20:00:00","gmt_time_end_last":"2018-01-22 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"600607":{"#nid":"600607","#data":{"type":"event","title":"ARC-TRIAD Seminar - Cong Han Lim (Wisconsin)","body":[{"value":"\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EARC-TRIAD\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003ECong Han Lim (Wisconsin)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EWednesday, January 17, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EGroseclose 402 - 10:00 am\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\u003ETowards Large-Scale Nonconvex\/Stochastic Discrete Optimization\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp; Modern data analytics is powered by scalable mathematical optimization methods. For decision-making, we want to be able to solve large-scale mathematical problems that include discrete choices or structures. These can already be very challenging to solve exactly even when the objective and feasible region are convex. We want to be able to model more general concepts that naturally lead to huge or nonconvex formulations, such as robustness to uncertainty, economic ideas like economies of scale, and physical concepts in engineering applications such as power systems and water network design.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;In this talk, I will present techniques for handling two such families of problems. I will demonstrate a new class of cutting planes for mixed-integer programs with separable concave costs and show that they can be combined with existing cuts for canonical mixed-integer linear sets. For stochastic mixed-integer programs, I will describe a new subgradient method for solving the dual decomposition that parallelizes significantly better than traditional subgradient on modern distributed and multi-core computer architectures. I will conclude by discussing some future directions in machine learning and (stochastic) mixed-integer programming.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/limconghan.github.io\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Towards Large-Scale Nonconvex\/Stochastic Discrete Optimization"}],"uid":"27544","created_gmt":"2018-01-10 13:32:13","changed_gmt":"2018-01-12 13:35:03","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-01-17T10:00:00-05:00","event_time_end":"2018-01-17T11:00:00-05:00","event_time_end_last":"2018-01-17T11:00:00-05:00","gmt_time_start":"2018-01-17 15:00:00","gmt_time_end":"2018-01-17 16:00:00","gmt_time_end_last":"2018-01-17 16:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}