{"349751":{"#nid":"349751","#data":{"type":"event","title":"ARC Colloquium: Seth Pettie\u2013University of Michigan","body":[{"value":"\u003Cp\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003EWeighted Matching on General Graphs: Faster and Simpler\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract :\u003C\/strong\u003E\u003Cbr \/\u003EWe present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs.\u0026nbsp; The algorithm runs in O(mn^{1\/2}log(nW)) time, where m, n, and W are the numbers of edges, vertices and maximum integer edge weight.\u0026nbsp; This bound matches the fastest algorithm for bipartite graphs and comes within a log(nW) factor of the Micali-Vazirani cardinality matching algorithm.\u0026nbsp;\u0026nbsp; In terms of running time our algorithm is just slightly faster than the previous best (Gabow and Tarjan, 1991) by a roughly (log n)^{1\/2} factor.\u0026nbsp; However, it is dramatically simpler to describe and analyze. \u003C\/p\u003E\u003Cp\u003EJoint work with Ran Duan (IIIS, Tsinghua) and Hsin-Hao Su (University of Michigan).\u0026nbsp; Manuscript available at \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1411.1919v2\u0022 title=\u0022http:\/\/arxiv.org\/abs\/1411.1919v2\u0022\u003Ehttp:\/\/arxiv.org\/abs\/1411.1919v2\u003C\/a\u003E.\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003ESeth Pettie received his Ph.D. in Computer Science from the University of Texas at Austin, in 2003.\u0026nbsp; From 2003-2006 he was an Alexander von Humboldt Postdoctoral Fellow at the Max Planck Institute for Computer Science, in Saarbruecken, Germany.\u0026nbsp; Since 2006 he has been a professor of Electrical Engineering and Computer Science at the University of Michigan, in Ann Arbor.\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003ESeth Pettie, Assoc. Prof. in Computer Science and Engineering University of Michigan, Ann Arbor \u003Ca href=\u0022http:\/\/web.eecs.umich.edu\/~pettie\u0022\u003Ehttp:\/\/web.eecs.umich.edu\/~pettie\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Seth Pettie presents a talk as part of the ARC Colloquium series."}],"uid":"27255","created_gmt":"2014-11-26 14:43:54","changed_gmt":"2017-04-13 21:21:01","author":"Josie Giles","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-03-23T14:00:00-04:00","event_time_end":"2015-03-23T15:00:00-04:00","event_time_end_last":"2015-03-23T15:00:00-04:00","gmt_time_start":"2015-03-23 18:00:00","gmt_time_end":"2015-03-23 19:00:00","gmt_time_end_last":"2015-03-23 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"hg_media":{"349761":{"id":"349761","type":"image","title":"Seth Pettie","body":null,"created":"1449245696","gmt_created":"2015-12-04 16:14:56","changed":"1475895075","gmt_changed":"2016-10-08 02:51:15","alt":"Seth Pettie","file":{"fid":"201053","name":"seth-pettie.jpg","image_path":"\/sites\/default\/files\/images\/seth-pettie_0.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/seth-pettie_0.jpg","mime":"image\/jpeg","size":575201,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/seth-pettie_0.jpg?itok=OM07Mg-H"}}},"media_ids":["349761"],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"9267","name":"ARC Colloquium"},{"id":"168003","name":"Seth Pettie"}],"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","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"349781":{"#nid":"349781","#data":{"type":"event","title":"ARC Colloquium: Jamie Morgenstern \u2013 Carnegie Mellon University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EApproximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe present a mechanism for computing asymptotically stable school optimal matchings, while guaranteeing that it is an asymptotic dominant strategy for every student to report their true preferences to the mechanism. Our main tool in this endeavor is differential privacy: we give an algorithm that coordinates a stable matching using differentially private signals, which lead to our truthfulness guarantee. This is the first setting in which it is known how to achieve nontrivial truthfulness guarantees for students when computing school-optimal matchings, assuming worst-case preferences (for schools and students) in large markets.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EJoint work with Sampath Kannan, Aaron Roth and Zhiwei Steven Wu: SODA 2015.\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EJamie Morgenstern presents a talk as part of the ARC Colloquium series on Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Jamie Morgenstern presents a talk as part of the ARC Colloquium series on Approximately Stable, School Optimal, and Student-Truthful Many-to-One Matchings (via Differential Privacy)"}],"uid":"27255","created_gmt":"2014-11-26 15:42:21","changed_gmt":"2017-04-13 21:21:01","author":"Josie Giles","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-02-02T12:00:00-05:00","event_time_end":"2015-02-02T13:00:00-05:00","event_time_end_last":"2015-02-02T13:00:00-05:00","gmt_time_start":"2015-02-02 17:00:00","gmt_time_end":"2015-02-02 18:00:00","gmt_time_end_last":"2015-02-02 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"hg_media":{"350121":{"id":"350121","type":"image","title":"Jamie Morgenstern","body":null,"created":"1449245702","gmt_created":"2015-12-04 16:15:02","changed":"1475895075","gmt_changed":"2016-10-08 02:51:15","alt":"Jamie Morgenstern","file":{"fid":"201079","name":"jamie-morgenstern.jpg","image_path":"\/sites\/default\/files\/images\/jamie-morgenstern_0.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/jamie-morgenstern_0.jpg","mime":"image\/jpeg","size":118123,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/jamie-morgenstern_0.jpg?itok=0rgxFoOG"}}},"media_ids":["350121"],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"9267","name":"ARC Colloquium"},{"id":"111071","name":"Jamie Morgenstern"}],"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":""}},"350151":{"#nid":"350151","#data":{"type":"event","title":"The Power of Randomness in Computation Workshop","body":[{"value":"\u003Cp\u003EARC presents\u0026nbsp;\u201c\u003Ca href=\u0022http:\/\/www.ima.umn.edu\/2014-2015\/W3.16-20.15\/?event_id=W3.16-20.15\u0022 target=\u0022_blank\u0022\u003EThe Power of Randomness in Computation Workshop\u003C\/a\u003E\u201d, co-sponsored by the\u0026nbsp;Institute for Mathematics and its Applications (IMA)\u0026nbsp;at the University of Minnesota.\u003C\/p\u003E\u003Cp\u003EThis workshop will be held at the Georgia Institute of Technology, Klaus Building room 1116, 266 Ferst Drive, NW, Atlanta, GA 30332-0765.\u003C\/p\u003E\u003Cp\u003EThis workshop will bring together researchers from a variety of fields to highlight new results broadly related to the use of randomization in algorithm design.\u003C\/p\u003E\u003Cp\u003ETalks will highlight new results in the area of randomized algorithms and probabilistic tools for algorithm design. The workshop will also include recent successes in derandomization and problems where there are efficient deterministic algorithms but not yet randomized versions, such as Weitz\u0027s approximate counting approach and recent extensions of it.\u003C\/p\u003E\u003Cp\u003EThe workshop will attempt to bring various experts interested in this general theme and identify challenging open problems and discuss ways to approach and attack them.\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EARC presents \u201c\u003Ca href=\u0022http:\/\/www.ima.umn.edu\/2014-2015\/W3.16-20.15\/?event_id=W3.16-20.15\u0022 target=\u0022_blank\u0022\u003EThe Power of Randomness in Computation Workshop\u003C\/a\u003E\u201d, co-sponsored by the Institute for Mathematics and its Applications (IMA\u003Ca href=\u0022http:\/\/www.ima.umn.edu\/\u0022 target=\u0022_blank\u0022\u003E)\u003C\/a\u003E at the University of Minnesota.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"ARC presents \u201cThe Power of Randomness in Computation Workshop,\u201d co-sponsored by the Institute for Mathematics and its Applications (IMA) at the University of Minnesota."}],"uid":"27255","created_gmt":"2014-11-26 16:55:16","changed_gmt":"2017-04-13 21:21:00","author":"Josie Giles","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-03-16T10:00:00-04:00","event_time_end":"2015-03-20T18:00:00-04:00","event_time_end_last":"2015-03-20T18:00:00-04:00","gmt_time_start":"2015-03-16 14:00:00","gmt_time_end":"2015-03-20 22:00:00","gmt_time_end_last":"2015-03-20 22:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.ima.umn.edu\/2014-2015\/W3.16-20.15\/?event_id=W3.16-20.15","title":"The Power of Randomness in Computation"},{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"},{"url":"http:\/\/www.ima.umn.edu\/","title":"Institute for Mathematics and its Applications"}],"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":"111081","name":"Institute for Mathematics and its Applications"},{"id":"111091","name":"The Power of Randomness in Computation Workshop"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"26411","name":"Training\/Workshop"}],"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 \/\u003E\u003Ca href=\u0022mailto:denton@cc.gatech.edu\u0022\u003Edenton@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"357761":{"#nid":"357761","#data":{"type":"event","title":"ARC Colloquium: Vitaly Feldman - IBM\/Simons Institute","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EPreserving Statistical Validity in Adaptive Data Analysis\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EA great deal of effort has been devoted to reducing the risk of spurious scientific discoveries resulting from misapplication of statistical data analysis. Existing approaches to ensuring validity of inferences drawn from data assume a fixed collection of hypotheses to be tested, or analysis to be applied, selected non-adaptively before the data are examined. In contrast, the practice of data analysis in scientific research is by its nature an adaptive process, in which new hypotheses are generated and new analyses are performed on the basis of data exploration and observed outcomes on the same data. We demonstrate a new approach for addressing the challenges of adaptivity based on insights from private data analysis. As an application we show how to safely reuse a holdout set a great many times without undermining its validation power, even when hypotheses, models, and algorithms are chosen adaptively.\u003C\/p\u003E\u003Cp\u003EJoint work with Cynthia Dwork, Moritz Hardt, Toni Pitassi, Omer Reingold and Aaron Roth.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EVitaly Feldman presents a talk as part of the ARC Colloquium series.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"ARC Colloquium: Vitaly Feldman"}],"uid":"27466","created_gmt":"2014-12-17 12:03:31","changed_gmt":"2017-04-13 21:20:53","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-01-26T12:00:00-05:00","event_time_end":"2015-01-26T13:00:00-05:00","event_time_end_last":"2015-01-26T13:00:00-05:00","gmt_time_start":"2015-01-26 17:00:00","gmt_time_end":"2015-01-26 18:00:00","gmt_time_end_last":"2015-01-26 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"112751","name":"(ARC)"},{"id":"114981","name":"Adaptive Data Analysis"},{"id":"111051","name":"Algorithm and Randomness Center"},{"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":""}},"359681":{"#nid":"359681","#data":{"type":"event","title":"ARC Colloquium: Blair Sullivan - North Carolina State University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003ERefreshments served in Klaus 2222 at 2 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ELooking for Structure in Real-World Networks\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EGraphs offer a natural representation of relationships within data -- for example, edges can be defined based on any user-defined measure of similarity (e.g. word frequencies, geographic proximity of observation, gene expression levels, or overlap in sample populations) or interaction (e.g. social friendship, communication, chemical bonds\/protein bindings, or migration). As such, network analysis is playing an increasingly important role in understanding the data collected in a wide variety of social, scientific, and engineering settings.\u0026nbsp; Unfortunately, efficient graph algorithms with guaranteed performance and solution quality are impossible in general networks (according to computational complexity).\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;One tantalizing approach to increasing scalability without sacrificing accuracy is to employ a suite of powerful (parameterized) algorithms developed by the theoretical computer science community which exploit specific forms of sparse graph structure to drastically reduce running time.\u0026nbsp; The applicability of these algorithms, however, is unclear, since the (extensive) research effort in network science to characterize the structure of real-world graphs has been primarily focused on either coarse, global properties (e.g., diameter) or very localized measurements (e.g., clustering coefficient) -- metrics which are insufficient for ensuring efficient algorithms.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;We discuss recent work on bridging the gap between network analysis and structural graph algorithms, answering questions like: Do real-world networks exhibit structural properties that enable efficient algorithms?\u0026nbsp; Is it observable empirically? Can sparse structure be proven for popular random graph models? How does such a framework help? Are the efficient algorithms associated with this structure relevant for common tasks such as evaluating communities, clustering and motifs? Can we reduce the (often super-exponential) dependence of these approaches on their structural parameters?\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EJoint work with E. Demaine, M. Farrell, T. Goodrich, N. Lemons, F. Reidl, P. Rossmanith, F. Sanchez Villaamil \u0026amp; S. Sikdar.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EBlair Sullivan presents a talk as part of the ARC Colloquiuim series.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"ARC Colloquium: Blair Sullivan"}],"uid":"27466","created_gmt":"2014-12-31 16:01:09","changed_gmt":"2017-04-13 21:20:51","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-02-16T12:00:00-05:00","event_time_end":"2015-02-16T13:00:00-05:00","event_time_end_last":"2015-02-16T13:00:00-05:00","gmt_time_start":"2015-02-16 17:00:00","gmt_time_end":"2015-02-16 18:00:00","gmt_time_end_last":"2015-02-16 18: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":"12781","name":"algorithms \u0026 randomness center"},{"id":"9267","name":"ARC Colloquium"},{"id":"118411","name":"Blair Sullivan"},{"id":"118401","name":"Looking for Structure in Real-World Networks"},{"id":"14673","name":"theory"}],"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":""}},"359741":{"#nid":"359741","#data":{"type":"event","title":"ARC Colloquium\/ACO Student Seminar: Peter Winkler \u2013 Dartmouth College","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Pizza will be served at 1pm in Skiles 005)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EPursuit on a Graph\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;Abstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EPursuit games---motivated historically by military tactics \u2013 are a natural for graphical settings, and take many forms.\u0026nbsp; We will present some recent results involving (among other things) drunks, Kakeya sets and a ``ketchup graph.\u0027\u0027\u0026nbsp; Lastly, we describe what we think is the most important open problem in the field.\u003Cbr \/\u003E \u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Peter Winkler is William Morrill Professor of Mathematics and Computer Science at Dartmouth College.\u0026nbsp; He is the author of about 150 research papers and holds a dozen patents in marine navigation, cryptolography, holography, gaming, optical networking, and distributed computing.\u0026nbsp; His research is primarily in combinatorics, probability, and the theory of computing, with forays into statistical physics.\u0026nbsp; He is a winner of the Mathematical Association of America\u0027s Lester R. Ford and David P. Robbins prizes.\u003C\/p\u003E\u003Cp\u003EDr. Winkler has also written two collections of mathematical puzzles, a book on cryptography in the game of bridge, and a portfolio of compositions for ragtime piano.\u0026nbsp; He\u0027s working on a new puzzle book.\u003C\/p\u003E\u003Cp\u003EARC: \u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/\u0022\u003Ehttp:\/\/www.arc.gatech.edu\/\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EPeter Winkler will be giving a joint ACR Colloquium and ACO Student Seminar on January 16, 2015 at 1:00 pm in Skiles Room 005. - See more at: \u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.bjAYe3Eq.dpuf\u0022 title=\u0022http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.bjAYe3Eq.dpuf\u0022\u003Ehttp:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-sem...\u003C\/a\u003E\u003C\/p\u003EPeter Winkler will be giving a joint ACR Colloquium and ACO Student Seminar on January 16, 2015 at 1:00 pm in Skiles Room 005. - See more at: http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.bjAYe3Eq.dpufPeter Winkler will be giving a joint ACR Colloquium and ACO Student Seminar on January 16, 2015 at 1:00 pm in Skiles Room 005. - See more at: http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.bjAYe3Eq.dpufPeter Winkler will be giving a joint ACR Colloquium and ACO Student Seminar on January 16, 2015 at 1:00 pm in Skiles Room 005. - See more at: http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.mXKxEKom.dpufPeter Winkler will be giving a joint ACR Colloquium and ACO Student Seminar on January 16, 2015 at 1:00 pm in Skiles Room 005. - See more at: http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.mXKxEKom.dpuf","format":"limited_html"}],"field_summary_sentence":[{"value":"Peter Winkler will be giving a joint ACR Colloquium and ACO Student Seminar on January 16, 2015 at 1:00 pm in Skiles Room 005. - See more at: http:\/\/www.cc.gatech.edu\/events\/arc-colloquium-and-joint-aco-student-seminar-peter-winkler#sthash.bjAYe3Eq.d"}],"uid":"27466","created_gmt":"2015-01-02 10:11:25","changed_gmt":"2017-04-13 21:20:51","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-01-16T12:00:00-05:00","event_time_end":"2015-01-16T13:00:00-05:00","event_time_end_last":"2015-01-16T13:00:00-05:00","gmt_time_start":"2015-01-16 17:00:00","gmt_time_end":"2015-01-16 18:00:00","gmt_time_end_last":"2015-01-16 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"109","name":"Georgia Tech"},{"id":"1808","name":"graduate students"},{"id":"113281","name":"Peter Winkler"},{"id":"14673","name":"theory"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1789","name":"Conference\/Symposium"}],"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\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"374251":{"#nid":"374251","#data":{"type":"event","title":"ARC Colloquium\/ML Seminar series: Elad Hazan - Princeton University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E(Please note that the talk will be held in MiRC 102 A \u0026amp; B and the refreshments will be served at the talk)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EProjection-free Optimization\u0026nbsp;and Online Learning\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EModern large data sets prohibit any super-linear time operations. This motivates the study of iterative optimization algorithms with low complexity per iteration. The computational bottleneck in applying state-of-the-art iterative methods is many times the so-called \u0022projection step\u0022.\u003Cbr \/\u003EWe consider projection-free optimization\/learning that replaces projections by more efficient linear optimization steps. We describe the first linearly-converging algorithm of this type for polyhedral sets and how it gives rise to optimal-rate stochastic optimization and online learning algorithms.\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Elad Hazan presents a talk as part of the ARC Colloquium series and co-sponsored by the Machine Learning Seminar Series"}],"uid":"27466","created_gmt":"2015-02-06 17:45:07","changed_gmt":"2017-04-13 21:20:08","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-03-25T15:00:00-04:00","event_time_end":"2015-03-25T16:00:00-04:00","event_time_end_last":"2015-03-25T16:00:00-04:00","gmt_time_start":"2015-03-25 19:00:00","gmt_time_end":"2015-03-25 20:00:00","gmt_time_end_last":"2015-03-25 20: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":"9267","name":"ARC Colloquium"},{"id":"9167","name":"machine learning"}],"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\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"380871":{"#nid":"380871","#data":{"type":"event","title":"ARC Colloquium: Nikhil Devanur - Microsoft Research","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EOnline Advertisements and Online Algorithms\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ECapacity or budget planning is an important component of any online ad serving platform. This has given rise to a rich and exciting line of work in online algorithms, and one of the most successful marriages of theory and practice. The practical aspects have directly influenced the theory and the theory has had significant impact on the design of modern advertising systems. The talk will give an overview of this interaction and some recent results on a very general problem called the online convex programming problem.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ENikhil R. Devanur is a researcher in the Theory group at Microsoft Research, Redmond. He is interested in designing algorithms that are faster, simpler, work online or in a distributed fashion, for some of the fundamental combinatorial optimization problem and in \u0022Automated Economics\u0022,\u0026nbsp; which studies the question of how technology can be used to improve the efficiency of economic systems. Prior to joining Microsoft Research, Nikhil got his PhD from Georgia Tech and spent a year at the Toyota Technological Institute at Chicago as a Research Assistant Professor.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Nikhil Devanur presents a talk as part of the ARC Colloquium series."}],"uid":"27466","created_gmt":"2015-02-23 11:04:30","changed_gmt":"2017-04-13 21:19:59","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-04-13T14:00:00-04:00","event_time_end":"2015-04-13T15:00:00-04:00","event_time_end_last":"2015-04-13T15:00:00-04:00","gmt_time_start":"2015-04-13 18:00:00","gmt_time_end":"2015-04-13 19:00:00","gmt_time_end_last":"2015-04-13 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50877","name":"School of Computational Science and Engineering"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"9267","name":"ARC Colloquium"}],"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\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"386111":{"#nid":"386111","#data":{"type":"event","title":"ARC Colloquium: Anup Rao - Yale University","body":[{"value":"\u003Cp\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cbr \/\u003EAlgorithms for Lipschitz Learning on Graphs\u003Cbr \/\u003E\u003Cbr \/\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E \u003Cbr \/\u003EWe develop fast algorithms for solving regression problems on graphs where one is given the value of a function at some vertices, and must find its smoothest possible extension to all vertices. The extension we compute is the absolutely minimal Lipschitz extension, and is the limit for large p of p-Laplacian regularization. We present an algorithm that computes a minimal Lipschitz extension in expected linear time, and an algorithm that computes an absolutely minimal Lipschitz extension in expected time O(mn). The latter algorithm has variants that seem to run much faster in practice. These extensions are particularly amenable to regularization: we can perform l_0 regularization on the given values in polynomial time and l_1 regularization on the graph edge weights in time O(m^(3\/2)). Our algorithms naturally extend to directed graphs.\u0026nbsp; This is a joint work with Rasmus Kyng, Sushant Sachdeva and Daniel Spielman.\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Anup Rao presents a talk as part of the ARC Colloquium series."}],"uid":"27466","created_gmt":"2015-03-09 16:57:38","changed_gmt":"2017-04-13 21:19:47","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-03-30T14:00:00-04:00","event_time_end":"2015-03-30T15:00:00-04:00","event_time_end_last":"2015-03-30T15:00:00-04:00","gmt_time_start":"2015-03-30 18:00:00","gmt_time_end":"2015-03-30 19:00:00","gmt_time_end_last":"2015-03-30 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"},{"url":"https:\/\/www.google.com\/maps\/place\/Klaus+Advanced+Computing+Building\/@33.777252,-84.396185,17z\/data=!3m1!4b1!4m2!3m1!1s0x87b781ec0ab42ea5:0x16eec927f37b40ec","title":"GA Tech, Klaus Building, Room 1116 West"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"112751","name":"(ARC)"},{"id":"114981","name":"Adaptive Data Analysis"},{"id":"111051","name":"Algorithm and Randomness Center"},{"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\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"393021":{"#nid":"393021","#data":{"type":"event","title":"ARC 7 (Annual Event) with Keynote by Christos Papadimitriou","body":[{"value":"\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003ESchedule\u003C\/strong\u003E:\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u0026nbsp;9:00 - 9:05\u0026nbsp; \u0026nbsp; \u0026nbsp; Introduction\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u0026nbsp;9:05 - 10:35 \u0026nbsp; \u0026nbsp;Talks by \u003Cstrong\u003ESrinivas Aluru\u003C\/strong\u003E (CSE),\u003Cstrong\u003E\u003Cstrong\u003E Santosh Vempala\u003C\/strong\u003E (CS), \u003C\/strong\u003Eand\u003Cstrong\u003E Natashia Boland\u003C\/strong\u003E (ISyE)\u0026nbsp; (30 minutes each)\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u0026nbsp;10:35 - 11:00\u0026nbsp; Break and light snacks\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u0026nbsp;11:00 - 12:00\u0026nbsp; Keynote by \u003Cstrong\u003EChristos Papadimitriou\u003C\/strong\u003E (U.C.- Berkeley)\u0026nbsp;\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E(see titles and abstracts below)\u003C\/p\u003E\u003Cp class=\u0022p4\u0022\u003E\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESrinivas Aluru, (CSE)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EParallel machine learning approaches for reverse engineering genome-scale networks\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EReverse engineering whole-genome networks from large-scale gene expression measurements and analyzing them to extract biologically valid hypotheses are important challenges in systems biology. While simpler models easily scale to large number of genes and gene expression datasets, more accurate models are compute intensive limiting their scale of applicability. In this talk, I will present our research on the development of parallel mutual information and Bayesian network based structure learning methods to eliminate such bottlenecks and facilitate genome-scale network structure learning.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESantosh Vempala, (CS)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003ESafe and Easy: Humanly Usable Password Generation Methods\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EOn a typical day, humans brush teeth, read, eat, converse ... and type passwords. This last task seems to be overly time-consuming (multiple attempts, frequent resets) and insecure --- passwords are often compromised. We desire passwords that are HUMANLY USABLE, i.e., easy to generate when needed, and SECURE, i.e., any single password is hard to crack, but even knowing several passwords doesn\u0027t allow an adversary infer others. Is this possible? How? How to even measure human effort? These questions lead us to ask what (protocols and algorithms) humans can compute and cannot compute. We present a model for measuring the complexity of human computation, and apply it in a rigorous framework for password generation.\u003C\/p\u003E\u003Cp\u003EThis is joint work with Manuel Blum.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ENatashia L Boland, (ISyE)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Alternating Projection Algorithms and Integer Programming\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E Alternating projection algorithms have been independently discovered, and have made a significant impact, in diverse areas of science and engineering. They remain of great interest and current activity in convex optimization, and were independently discovered for general-purpose integer programming (IP) in 2005. Their use has been one component of the major advances in IP technology that now make IP a valuable and practical tool for solution of large-scale industrial problems. An essential element of the success of these methods is the application of randomization within the alternating projection framework.\u0026nbsp; Since their first discovery for IP, the methods have been improved and extended in a number of directions. In this talk, we will give an overview of recent activity in these methods, including two new ideas for improving their performance.\u003C\/p\u003E\u003Cp\u003E\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EKeynote Speaker\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EChristos H \u003C\/strong\u003E\u003Cstrong\u003EPapadimitriou, \u003C\/strong\u003E\u003Cstrong\u003EUC-Berkeley\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Life under the lens\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E Applying the algorithmic point of view to the natural, life, and social sciences often results in unexpected insights and progress in central problems, a mode of research that has been described as ``the lens of computation.\u0027\u0027\u0026nbsp; I will focus on examples in the life sciences, from joint work with Erick Chastain, Costis Daskalakis, Adi Livnat, Umesh Vazirani, Santosh Vempala, and Albert Wu:\u0026nbsp; Evolution of a population through sexual reproduction can be rethought of as a repeated game between genes played through the multiplicative weight updates algorithm.\u0026nbsp; In an infinite population, when selection acts not on genes alone but on pairs of genes, fixation can take exponentially many generations.\u0026nbsp; And unsupervised learning of patterns can be achieved spontaneously and with high probability through a simple and neurally plausible primitive. \u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EBio:\u003C\/strong\u003E Christos H. Papadimitriou is the C. Lester Hogan Professor of Computer Science at UC-Berkeley.\u0026nbsp; Before joining Berkeley in 1996, he taught at Harvard, MIT, NTU Athens, Stanford, and UCSD.\u0026nbsp; He has written five textbooks and many articles on algorithms and complexity, and their applications to optimization, databases, control, AI, robotics, economics, game theory, the Internet, evolution, and brain science.\u0026nbsp; He holds a PhD from Princeton, and seven honorary doctorates.\u0026nbsp; He is a member of the National Academy of Sciences of the US, the American Academy of Arts and Sciences, and the National Academy of Engineering. He has also written three novels: \u201cTuring\u201d, \u201cLogicomix\u201d (with Apostolos Doxiadis) and \u201cIndependence\u201d (in Greek).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EThe Algorithms \u0026amp; Randomness Center presents the annual ARC Day with Keynote speaker Christos Papadimitriou of U.C. Berkeley, along with talks by Srinivas Aluru (CSE), Natashia Boland (ISyE) and Santosh Vempala (CS).\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Title:  Life Under the Lens"}],"uid":"27466","created_gmt":"2015-04-01 17:41:12","changed_gmt":"2017-04-13 21:19:34","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-04-17T10:00:00-04:00","event_time_end":"2015-04-17T13:00:00-04:00","event_time_end_last":"2015-04-17T13:00:00-04:00","gmt_time_start":"2015-04-17 14:00:00","gmt_time_end":"2015-04-17 17:00:00","gmt_time_end_last":"2015-04-17 17: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":"109","name":"Georgia Tech"},{"id":"1808","name":"graduate students"},{"id":"14673","name":"theory"}],"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\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022mailto:denton@cc.gatech.edu\u0022\u003Edenton@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"436081":{"#nid":"436081","#data":{"type":"event","title":"ARC Colloquium: Andreas Galanis - University of Oxford","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) Colloquium\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAndreas Galanis\u0026nbsp;\u2013\u0026nbsp;University of Oxford\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, August 26, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 2447 - 2:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;Title:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESwendsen-Wang Algorithm on the Mean-Field Potts Model\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThis talk will focus on the q-state ferromagnetic Potts model on the n-vertex complete graph known as the mean-field (Curie-Weiss) model. We analyze the Swendsen-Wang algorithm which is a Markov chain that utilizes the random cluster representation for the ferromagnetic Potts model to recolor large sets of vertices in one step and potentially overcomes obstacles that inhibit single-site Glauber dynamics.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The case q=2 (the Swendsen-Wang algorithm for the ferromagnetic Ising model) undergoes a slow-down at a critical temperature beta=betac (Long et al., 2014), but yet still has polynomial mixing time at all (inverse) temperatures beta\u0026gt;0 (Cooper et al., 2000).\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In contrast, for q\u0026gt;=3 there are two critical temperatures 0\u0026lt;betau\u0026lt;betarc that are relevant (these correspond to phase transitions on the infinite tree). We prove that the mixing time of the Swendsen-Wang algorithm for the ferromagnetic Potts model on the n-vertex complete graph satisfies:\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E(i) O(log n) for beta\u0026lt;betau, (ii) O(n^{1\/3}) for beta=betau, (iii) exp(n^(Omega(1))) for betau\u0026lt;beta\u0026lt;betarc, and (iv) O(log n) for beta\u0026gt;=betarc.\u0026nbsp;These results complement refined results of Cuff et al. (2012) on the mixing time of the Glauber dynamics for the ferromagnetic Potts model.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The most interesting aspect of our analysis is at the critical temperature beta=betau, which requires a delicate choice of a potential function to balance the conflating factors for the slow drift away from a fixed point (which is repulsive but not Jacobian repulsive): close to the fixed point the variance from the percolation step dominates and sufficiently far from the fixed point the dynamics of the size of the dominant color class takes over.\u003C\/p\u003E\u003Cp\u003EJoint work with Daniel Stefankovic and Eric Vigoda.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 2447 at 4 pm (Note: time and location are different than usual)"}],"uid":"27466","created_gmt":"2015-08-18 13:42:48","changed_gmt":"2017-04-13 21:18:45","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-08-26T15:05:00-04:00","event_time_end":"2015-08-26T16:00:00-04:00","event_time_end_last":"2015-08-26T16:00:00-04:00","gmt_time_start":"2015-08-26 19:05:00","gmt_time_end":"2015-08-26 20:00:00","gmt_time_end_last":"2015-08-26 20: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":"112751","name":"(ARC)"},{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"168064","name":"Swendsen-Wang algorithm"}],"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\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"436141":{"#nid":"436141","#data":{"type":"event","title":"ARC Colloquium Joint with ACO: Richard Peng - Georgia Tech","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) and ACO Joint \u0026nbsp;Colloquium\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003ERichard Peng\u0026nbsp;\u2013\u0026nbsp;Georgia Tech\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, August 31, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u0026amp; 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:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAlgorithm Frameworks Based on Structure Preserving Sampling\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESampling is a widely used algorithmic tool: running routines on a small representative subset of the data often leads to speedups while preserving accuracy. Recent works on algorithmic frameworks that relied on sampling graphs and matrices highlighted several connections between graph theory, statistics, optimization, and functional analysis. This talk will describe some key ideas that emerged from these connections:\u003C\/p\u003E\u003Cp\u003E*\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Sampling as a generalized divide-and-conquer paradigm.\u003C\/p\u003E\u003Cp\u003E*\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Implicit sampling without constructing the larger data set, and its algorithmic applications.\u003C\/p\u003E\u003Cp\u003E*\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; What does sampling need to preserve? What can sampling preserve?\u003C\/p\u003E\u003Cp\u003EThese ideas have applications in solvers for structured linear systems, network flow algorithms, input-sparsity time numerical routines, coresets, and dictionary learning.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 East \u0026 West at 1 pm"}],"uid":"27466","created_gmt":"2015-08-18 14:16:04","changed_gmt":"2017-04-13 21:18:45","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-08-31T14:00:00-04:00","event_time_end":"2015-08-31T15:00:00-04:00","event_time_end_last":"2015-08-31T15:00:00-04:00","gmt_time_start":"2015-08-31 18:00:00","gmt_time_end":"2015-08-31 19:00:00","gmt_time_end_last":"2015-08-31 19: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\u003C\/p\u003E\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"438131":{"#nid":"438131","#data":{"type":"event","title":"ARC Colloquium: Charilaos Efthymiou - Georgia Tech","body":[{"value":"\u003Cp\u003ENote: Talk will be held in Marcus 1117-1118.\u003C\/p\u003E\u003Ch6 align=\u0022center\u0022\u003E\u003Cstrong\u003E\u0026nbsp;Algorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/h6\u003E\u003Ch5 align=\u0022center\u0022\u003ECharilaos Efthymiou \u2013 Georgia Tech\u003C\/h5\u003E\u003Ch6 align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 14, 2015\u003C\/strong\u003E\u003C\/h6\u003E\u003Ch6 align=\u0022center\u0022\u003E\u003Cstrong\u003EMarcus 1117 \u0026amp; 1118 - 1:00 pm\u003C\/strong\u003E\u003C\/h6\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:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EReconstruction thresholds for the random colourings of G(n,m)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn this talk we consider the reconstruction problem for the random colourings of a random graph G(n,m) of\u0026nbsp; degree d.\u003C\/p\u003E\u003Cp\u003EFor some k-colourable graph G,\u0026nbsp; the reconstruction problem studies the correlation between the assignment of a single vertex in G and that of its neighbours at distance r, under the uniform measure over the k-colourings of G. This is point to set correlation.\u003C\/p\u003E\u003Cp\u003EWhen the correlation persists as r grows, then we have reconstruction, otherwise we have non-reconstruction.\u003C\/p\u003E\u003Cp\u003EIt has been conjecture from statistical physics that for typical instances of G(n,m)\u0026nbsp; the transition from non-reconstruction to reconstruction exhibits a threshold behavior. That is, there is a critical value k_0, which depends on the expected degree d, such that the following is true:\u0026nbsp; When k\u0026gt;k_0 there is non-reconstruction while when k\u0026lt;k_0 there is reconstruction.\u003C\/p\u003E\u003Cp\u003EThe aforementioned phase transition has been related to the performance of local search algorithms as well as the shattering phenomenon in the solution space of the k-colourings.\u003C\/p\u003E\u003Cp\u003EIn this talk I discuss our recent results which show that the phase transition from statistical physics is indeed correct. Moreover, the point where this phase transition occurs, up to smaller order terms, is exactly at the point where it has been conjectured to be.\u003C\/p\u003E\u003Cp\u003EThe first step in our approach is to show that the Gibbs distribution over the k-colouring of G(n,m) converges locally to the Gibbs distribution over the k-colourings of a Poisson(d) Galton-Watson tree\u0026nbsp; T(d), for a wide range of\u0026nbsp; k. This allows to reduce our initial problem to studying the reconstruction on T(d). The second step is to establish the reconstruction threshold for the colourings of T(d).\u003C\/p\u003E\u003Cp\u003EThis talk is based on 2 recent works of mine.\u0026nbsp; One of them is a joint work with Amin Coja-Oghlan and Nor Jaafari.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Marcus 1117 \u0026 1118 at 1 pm (Note: different location)"}],"uid":"27466","created_gmt":"2015-08-20 15:28:05","changed_gmt":"2017-04-13 21:18:39","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-14T14:00:00-04:00","event_time_end":"2015-09-14T15:00:00-04:00","event_time_end_last":"2015-09-14T15:00:00-04:00","gmt_time_start":"2015-09-14 18:00:00","gmt_time_end":"2015-09-14 19:00:00","gmt_time_end_last":"2015-09-14 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"438751":{"#nid":"438751","#data":{"type":"event","title":"ARC Colloquium: Christine Heitsch - Georgia Tech","body":[{"value":"\u003Ch2 align=\u0022center\u0022\u003EChristine Heitsch \u2013 Georgia Tech\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 21, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 W - 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(\u003C\/strong\u003E\u003Cstrong\u003ERefreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003ETitle: \u0026nbsp;\u0026nbsp; \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EStrings, Trees, and RNA Folding\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAn RNA molecule is a linear biochemical chain which folds into a three dimensional structure via a set of 2D base pairings known as a nested secondary structure.\u0026nbsp; Reliably determining a secondary structure for large RNA molecules, such as the genomes of most viruses, is an important open problem in molecular biology.\u0026nbsp; Using strings and (plane) trees as a combinatorial model of RNA folding, we give mathematical results which yield insights into RNA branching configurations and suggest new directions in understanding the structure of RNA viruses.\u0026nbsp; We also demonstrate that, under a suitable abstraction, complex biological problems can reveal surprising mathematical structure.\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-08-21 17:21:41","changed_gmt":"2017-04-13 21:18:38","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-21T14:00:00-04:00","event_time_end":"2015-09-21T15:00:00-04:00","event_time_end_last":"2015-09-21T15:00:00-04:00","gmt_time_start":"2015-09-21 18:00:00","gmt_time_end":"2015-09-21 19:00:00","gmt_time_end_last":"2015-09-21 19: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":""}},"438761":{"#nid":"438761","#data":{"type":"event","title":"ARC Colloquium: Nicole Immorlica - Microsoft Research New England","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003ENicole Immorlica - Microsoft Research New England\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 2, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West \u2013 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe Emergent Structure of Simple Behaviors in Complex Networks\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMany games of social significance are played in a networked context.\u0026nbsp; In these settings, agents often exhibit simple behaviors, shaped by local preferences and social norms.\u0026nbsp; The interplay of these behaviors and the underlying network give rise to emergent structures with global impact.\u0026nbsp; In this talk, we explore the impact of networked behavior on social capital, segregation, and learning.\u003C\/p\u003E\u003Cp\u003EFirst we study the emergence of social capital in dynamic, anonymous social networks, such as online communities.\u0026nbsp; We find that, despite the lack of punitive strategies, (partial) cooperation is sustainable at an intuitive and simple equilibrium as cooperation allows an individual to interact with an increasing number of other cooperators, resulting in the formation of valuable social capital.\u003C\/p\u003E\u003Cp\u003ENext we examine the emergence of segregation in geographical networks.\u0026nbsp; In 1969, Schelling introduced a model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority and suggested that this local behavior can cause global segregation effects. Our rigorous analysis shows that, in contrast to prior interpretations, the outcome exhibits local but not global segregation.\u003C\/p\u003E\u003Cp\u003EFinally, we study learning outcomes in social networks. Individuals with independent opinions asynchronously update their declared opinion to match the majority report of their neighbors.\u0026nbsp; We show that the population will converge to the majority opinion with high probability if the underlying network is large, sparse, and expansive, properties reflected by realistic social networks.\u003C\/p\u003E\u003Cp\u003EBased on joint works with Christie Brandt, Michal Feldman, Gautam Kamath, Robert Kleinberg, Brendan Lucier, Brian Rogers and Matt Weinberg.\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-08-21 17:25:36","changed_gmt":"2017-04-13 21:18:38","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-11-02T12:00:00-05:00","event_time_end":"2015-11-02T13:00:00-05:00","event_time_end_last":"2015-11-02T13:00:00-05:00","gmt_time_start":"2015-11-02 17:00:00","gmt_time_end":"2015-11-02 18:00:00","gmt_time_end_last":"2015-11-02 18: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\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":""}},"444651":{"#nid":"444651","#data":{"type":"event","title":"ARC Colloquium: Dan Gusfield - UC Davis","body":[{"value":"\u003Cp\u003EPlease note: talk is at 4 pm on Wednesday.\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u0026nbsp;\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EDan Gusfield - UC Davis\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, September 9, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 4:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in 1116W at 4 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EPhylogenetics Through the Lens of Chordal Graph Theory\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe evolutionary history of a set of species is generally described by a hylogenetic tree.\u0026nbsp; The combinatorial structure of phylogenetic trees is very well understood when biological characters can only take on two states. But, when characters can take on more than two states, the combinatorial structure is much less understood. The Multi-State Perfect Phylogeny (MPP) problem addresses the case of \u0026nbsp;non-binary states.\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EThe MPP problem was initially defined (using different terminology) in a 1975 paper by Peter Buneman that establishes a deep relationship between the MPP problem and the class of graphs called chordal graphs. It showed a how to view the multi-state perfect phylogeny problem as a problem of triangulating non-chordal graphs. While that result has been used in mathematical results, it was not widely exploited as a computational tool.\u003C\/p\u003E\u003Cp\u003EIn this talk, I discuss our work on exploiting the chordal graph approach to solve and study multi-state perfect phylogeny and related problems.\u0026nbsp; I will discuss how the problem relates to minimal triangulation, 2-SAT, integer linear programming, and undirected tree compatibility.\u0026nbsp; I will also discuss generalizations of the classic four-gametes condition, which characterizes a binary (perfect) phylogeny, to conditions that characterize multi-state perfect phylogenies, and I will identify open questions in this field.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EDan Gusfield of UC Davis will give a talk at the ARC Center Colloquium on Sept. 9 at 4 pm in Klaus 1116 West.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Klaus 1116 West at 4 pm  (Note: different day and time.)"}],"uid":"27466","created_gmt":"2015-09-04 08:48:16","changed_gmt":"2017-04-13 21:18:23","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-09T17:00:00-04:00","event_time_end":"2015-09-09T18:00:00-04:00","event_time_end_last":"2015-09-09T18:00:00-04:00","gmt_time_start":"2015-09-09 21:00:00","gmt_time_end":"2015-09-09 22:00:00","gmt_time_end_last":"2015-09-09 22:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"140451","name":"Phylogenetics Through the Lens of Chordal Graph Theory"}],"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\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"445161":{"#nid":"445161","#data":{"type":"event","title":"ARC\/ACO Colloquium: Alan Frieze - Carnegie Mellon University","body":[{"value":"\u003Cp\u003EPlease note the talk is at \u003Cstrong\u003E11 am\u003C\/strong\u003E in \u003Cstrong\u003E1116 East\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAlan Frieze \u2013 Carnegie Mellon University\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EWednesday, September 23, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 E - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at Noon)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ETitle: Probabilistic analysis of some combinatorial optimization problems.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe consider the following probabilistic model. The edges of a (complete) graph have unknown random edge weights. We want to build a minimum cost structure. We can ask for the weight of an edge and then accept or reject the edge. Once rejected, the edge cannot be accepted later. We must accept enough edges to support a structure and we are charged for all the edges accepted, even if not used. We give results in this model for minimum spanning tree, perfect matching and shortest path.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;Joint work with Colin Cooper and Wesley Pegden.\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 at 11 am  (Note: different day, time and location)"}],"uid":"27466","created_gmt":"2015-09-04 17:37:44","changed_gmt":"2017-04-13 21:18:22","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-23T12:00:00-04:00","event_time_end":"2015-09-23T13:00:00-04:00","event_time_end_last":"2015-09-23T13:00:00-04:00","gmt_time_start":"2015-09-23 16:00:00","gmt_time_end":"2015-09-23 17:00:00","gmt_time_end_last":"2015-09-23 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.math.cmu.edu\/~af1p\/","title":"Alan Frieze"},{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"},{"id":"140651","name":"Probabilistic Combinatorics"},{"id":"140661","name":"Theoretical Computer Science and Operations Research"}],"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\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"446251":{"#nid":"446251","#data":{"type":"event","title":"ARC Colloquium: Anup Rao - Georgia Tech","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAnup Rao \u2013 Georgia Tech\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 26, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West \u2013 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe Stochastic Block Model and Communities in Sparse Random Graphs: Detection at Optimal Rate\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe consider the problem of communities detection in sparse random graphs. Our model is the so-called Stochastic Block Model, which has been immensely popular in the recent statistics literature. Let X1,...Xk be vertex sets of size n each (where k is fixed and n is large). One draws random edges inside each Xi with probability a\/n, and between Xi and Xj with probability b\/n, for some constants a and b. Given one instance of this sparse random graph, our goal is to recover the sets Xi as correctly as possible. We are going to present a fast spectral algorithm which does this job at the optimal rate (namely the relation between a,b and the number of mistakes in the recovery is optimal). Our algorithm is based on spectral properties of random sparse matrices and is easy to implement. We will also discuss some related works with spectral algorithms and an open question concerning random matrices.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-10 09:44:12","changed_gmt":"2017-04-13 21:18:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-10-26T14:00:00-04:00","event_time_end":"2015-10-26T15:00:00-04:00","event_time_end_last":"2015-10-26T15:00:00-04:00","gmt_time_start":"2015-10-26 18:00:00","gmt_time_end":"2015-10-26 19:00:00","gmt_time_end_last":"2015-10-26 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"446271":{"#nid":"446271","#data":{"type":"event","title":"ARC Colloquium: Yitong Yin \u2013 Nanjing University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EYitong Yin \u2013 Nanjing University\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 28, 2015\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: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ECounting hypergraph matchings up to uniqueness threshold\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe study the problem of approximately counting hypergraph matchings with an activity parameter $\\lambda$ in hypergraphs of bounded maximum degree and bounded maximum size of hyperedges. This problem unifies two important statistical physics models in approximate counting: the hardcore model (graph independent sets) and the monomer-dimer model (graph matchings).\u003C\/p\u003E\u003Cp\u003EWe show for this model the critical activity $\\lambda_c= \\frac{d^d}{k (d-1)^{d+1}}$ is the threshold for the uniqueness of Gibbs measures on the infinite $(d+1)$-uniform $(k+1)$-regular hypertree. And we show that when $\\lambda\u0026lt;\\lambda_c$ the model exhibits strong spatial mixing at an exponential rate and there is an FPTAS for the partition function of the model on all hypergraphs of maximum degree at most $k+1$ and maximum \u0026nbsp;edge size at most $d+1$. Assuming NP$\\neq$RP, there is no FPRAS for the partition function of the model when $\\lambda \u0026gt; 2\\lambda_c$ on above family of hypergraphs .\u003C\/p\u003E\u003Cp\u003ETowards closing this gap and obtaining a tight transition of approximability, we study the local weak convergence from an infinite sequence of random finite hypergraphs to the infinite uniform regular hypertree with specified symmetry, and prove a surprising result: the existence of such local convergence is fully characterized by the reversibility of the uniform random walk on the infinite hypertree projected on the symmetry classes. We also give explicit constructions sequence of random finite hypergraphs with proper local convergence property when the reversibility condition is satisfied.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-10 09:47:51","changed_gmt":"2017-04-13 21:18:21","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-09-28T14:00:00-04:00","event_time_end":"2015-09-28T15:00:00-04:00","event_time_end_last":"2015-09-28T15:00:00-04:00","gmt_time_start":"2015-09-28 18:00:00","gmt_time_end":"2015-09-28 19:00:00","gmt_time_end_last":"2015-09-28 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"}],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"448851":{"#nid":"448851","#data":{"type":"event","title":"ARC Colloquium: David P. Woodruff - IBM","body":[{"value":"\u003Ch2 align=\u0022center\u0022\u003EDavid P. Woodruff - IBM\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 9, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West \u2013 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EInput Sparsity Time Algorithms for Robust Regression and Robust Low Rank Approximation\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe give near optimal algorithms for regression and low rank approximation in the robust case. For regression, we give algorithms generalizing l_p regression to M-Estimator loss functions, such as the Huber measure, which enjoys the robustness properties of l_1 as well as the smoothness properties of l_2. For low rank approximation, we give new algorithms generalizing the singular value decomposition to sum of p-th powers of distances, and M-estimator loss functions applied to the distances. Some problems here are arguably even more fundamental than the SVD itself, such as given a set of points, find a line which minimizes the sum of distances of the points to the line, rather than the sum of squared distances. These measures are less sensitive to outliers and we show they can be computed approximately in time proportional to the number of non-zeros of the input matrix. We also discuss hardness results in the low rank approximation setting.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-16 14:39:24","changed_gmt":"2017-04-13 21:18:16","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-11-09T12:00:00-05:00","event_time_end":"2015-11-09T13:00:00-05:00","event_time_end_last":"2015-11-09T13:00:00-05:00","gmt_time_start":"2015-11-09 17:00:00","gmt_time_end":"2015-11-09 18:00:00","gmt_time_end_last":"2015-11-09 18: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"},{"id":"1126","name":"ibm"},{"id":"9167","name":"machine learning"}],"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":""}},"449061":{"#nid":"449061","#data":{"type":"event","title":"ARC Colloquium: James Saunderson","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\u003EJames Saunderson - University of Washington\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, November 23, 2015\u003Cbr \/\u003EKlaus 1116 West \u2013 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: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESemidefinite descriptions of regular polygons (and beyond)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESemidefinite programs are a family of convex optimization problems that generalize linear programs and can model a wide range of problems from areas as diverse as statistics, robotics, and combinatorial optimization. Despite this, understanding the expressive power and limitations of (small) semidefinite programs remains a significant challenge.\u003C\/p\u003E\u003Cp\u003EThis talk is centered on new efficient descriptions of regular polygons (and related polytopes) in terms of the feasible regions of semidefinite programs. These constructions, for instance, give the first known family of polytopes with semidefinite programming descriptions that are asymptotically smaller than the best linear programming descriptions.\u003C\/p\u003E\u003Cp\u003EBased on joint work with Hamza Fawzi (MIT) and Pablo Parrilo (MIT).\u003C\/p\u003E\u003Cp\u003EHost is Greg Blekherman (\u003Ca href=\u0022mailto:greg@math.gatech.edu\u0022\u003Egreg@math.gatech.edu\u003C\/a\u003E).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2015-09-17 11:26:14","changed_gmt":"2017-04-13 21:18:14","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-11-23T12:00:00-05:00","event_time_end":"2015-11-23T13:00:00-05:00","event_time_end_last":"2015-11-23T13:00:00-05:00","gmt_time_start":"2015-11-23 17:00:00","gmt_time_end":"2015-11-23 18:00:00","gmt_time_end_last":"2015-11-23 18: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":""}},"453411":{"#nid":"453411","#data":{"type":"event","title":"ARC Colloquium: Andrea Richa - Arizona State University","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Ch2 align=\u0022center\u0022\u003EAndrea W. Richa \u2013 Arizona State University\u003C\/h2\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EFriday, October 9, 2015\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East \u2013 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EProgrammable Matter: Self-organizing Particle Systems\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFrom the level of chemical reaction networks within cells to the social structures of higher organisms, biological systems take advantage of distributed computation to perform a myriad of complex functions. Computer\u0026nbsp; scientists and engineers have investigated biological and physical systems in order to understand how these systems can provide us with the necessary insight to realize self-organizing systems of artificial, programmable particles. Those investigations led to the notion of programmable matter. The impact of programmable matter will be seen across all areas, from improved drugs and assistance in nano surgery, to increased productivity, greater capabilities in automation, etc. Fully distributed computation, self-organization and self-stabilization are key for the scalability and robustness of such systems. In this talk, we present a general abstract model for programmable matter consisting of systems of simple, computationally-limited particles. We present self-organizing algorithms for the problems of leader election, coating, and shape formation.\u003C\/p\u003E\u003Cp\u003EThis work has been done in collaboration with Zahra Derakhshandeh (ASU), Christian Scheideler, Robert Gmyr and Thim Strothmann (U. of Paderborn, Germany), and others.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAndrea W. Richa is an Associate Professor in Computer Science at Arizona State University (ASU), Tempe, AZ. She is also affiliated with the Biomimicry Center at ASU. She received her M.S. and Ph.D. degrees from the School of Computer Science at Carnegie Mellon University, in 1995 and 1998, respectively. Prof. Richa\u0027s work on distributed algorithms has been widely cited, and includes work on self-organizing particle systems, wireless network modeling and topology control, wireless jamming, data mule networks, underwater optical networking, distributed load balancing, and distributed hash tables (DHTs). Dr. Richa was the recipient of an NSF CAREER Award in 1999, is currently an Associate Editor of IEEE Transactions on Mobile Computing, and has served as keynote speaker and program\\general chair of several prestigious conferences. Dr. Richa is also a founding member of UON Technologies. For a selected list of her publications and other accomplishments, and current research projects, please visit \u003Ca href=\u0022http:\/\/www.public.asu.edu\/~aricha\u0022\u003Ewww.public.asu.edu\/~aricha\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 East at 11:00 am"}],"uid":"27466","created_gmt":"2015-09-29 11:41:15","changed_gmt":"2017-04-13 21:18:06","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2015-10-09T12:00:00-04:00","event_time_end":"2015-10-09T13:00:00-04:00","event_time_end_last":"2015-10-09T13:00:00-04:00","gmt_time_start":"2015-10-09 16:00:00","gmt_time_end":"2015-10-09 17:00:00","gmt_time_end_last":"2015-10-09 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/www.arc.gatech.edu\/","title":"Algorithms \u0026 Randomness Center (ARC)"},{"url":"http:\/\/www.public.asu.edu\/~aricha","title":"Andrea W. Richa \u2013 Arizona State University"}],"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":""}}}