{"72861":{"#nid":"72861","#data":{"type":"event","title":"ARC Colloquium: Mihalis Yannakakis, Columbia University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1\/epsilon), where epsilon \u0026gt; 0 is the desired additive error bound of the solution.\u0026nbsp; (The model of computation is the standard Turing machine model.)\u003C\/p\u003E\u003Cp\u003EWe use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and heavily studied stochastic processes, including multi-type branching processes and stochastic context-free grammars.\u003C\/p\u003E\u003Cp\u003E(Joint work with Kousha Etessami and Alistair Stewart.)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMihalis Yannakakis is the Percy K. and Vida L. W. Hudson Professor of Computer Science \u003Cbr \/\u003Eat Columbia University. Prior to joining Columbia, he was Director of the Computing Principles Research Department at Bell Labs and at Avaya Labs, and Professor of Computer Science at Stanford University.\u003C\/p\u003E\u003Cp\u003EDr. Yannakakis received his PhD from Princeton University. His research interests include algorithms, complexity, optimization, game theory, databases, testing and verification. He has served on the editorial boards of several journals, including as the past editor-in-chief of the SIAM Journal on Computing, and has chaired various conferences, including the IEEE Symposium on Foundations of Computer Science, the ACM Symposium on Theory of Computing and the ACM Symposium on Principles of Database Systems. \u003Cbr \/\u003EDr. Yannakakis is a member of the National Academy of Engineering, a recipient of the Knuth Prize, a Fellow of the ACM, and a Bell Labs Fellow. \u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars"}],"uid":"27263","created_gmt":"2011-11-17 09:19:57","changed_gmt":"2016-10-08 01:56:41","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-12-07T12:30:00-05:00","event_time_end":"2011-12-07T12:30:00-05:00","event_time_end_last":"2011-12-07T12:30:00-05:00","gmt_time_start":"2011-12-07 17:30:00","gmt_time_end":"2011-12-07 17:30:00","gmt_time_end_last":"2011-12-07 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"72895":{"#nid":"72895","#data":{"type":"event","title":"ARC Colloquium: Robert Kleinberg, Cornell University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe resilience of networks to various types of failures is an undercurrent in many parts of graph theory and network algorithms. In this paper we study the resilience of networks in the presence of cascading failures \u2014 failures that spread from one node to another across the network structure. One finds such cascading processes at work in the kind of contagious failures that spread among financial institutions during a financial crisis, through nodes of a power grid or communication network during a widespread outage, or through a human population during the outbreak of an epidemic disease.\u003C\/p\u003E\u003Cp\u003EA widely studied model of cascades in networks assumes that each node of the network has an independent random threshold specifying the number of its neighbors that must fail in order for it to fail.\u0026nbsp; It turns out that when selecting among a set of graphs to minimize the failure probability of the most vulnerable node, the optimum graph structure depends quite intricately on the distribution of thresholds.\u0026nbsp; We develop several techniques for minimizing the maximum failure probability among d-regular graphs.\u0026nbsp; For d=2 we are able to solve the problem completely: the optimal graph is always a clique (i.e. triangle) or tree (i.e. infinite path), although which graph is better exhibits a surprising non-monotonicity as the threshold parameters vary.\u0026nbsp; When d is greater than 2 we present a technique based on power-series expansions of the failure probability that allows us to compare graphs in certain parts of the parameter space, deriving conclusions including the fact that as the threshold distribution varies, at least three different graphs are optimal among d-regular graphs. In particular, the set of optimal graphs here includes one which is neither a clique nor a tree.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;This is joint work with Larry Blume, David Easley, Jon Kleinberg, and Eva Tardos.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Which Networks are Least Susceptible to Cascading Failures?"}],"uid":"27263","created_gmt":"2011-11-21 12:09:12","changed_gmt":"2016-10-08 01:56:41","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-12-05T12:30:00-05:00","event_time_end":"2011-12-05T12:30:00-05:00","event_time_end_last":"2011-12-05T12:30:00-05:00","gmt_time_start":"2011-12-05 17:30:00","gmt_time_end":"2011-12-05 17:30:00","gmt_time_end_last":"2011-12-05 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"72405":{"#nid":"72405","#data":{"type":"event","title":"ARC Colloquium: Ruta Mehta, IIT, Bombay","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E Using the powerful machinery of the linear complementarity problem and Lemke\u0027s algorithm, we give a practical algorithm for computing an equilibrium for Fisher and Arrow-Debreu markets under\u0026nbsp;separable, piecewise-linear concave (SPLC) utilities, despite the PPAD-completeness of\u0026nbsp;this case.\u003C\/p\u003E\u003Cp\u003EIn 1975, Eaves had given such an algorithm for the case of linear utilities and had asked for an extension to the piecewise-linear, concave case. Our result settles his problem as well as the problem of Vazirani and Yannakakis of obtaining a path following algorithm for SPLC markets, thereby giving a direct proof of membership of this case in PPAD.\u003C\/p\u003E\u003Cp\u003EWe also prove that SPLC markets have an odd number of equilibria (up to scaling),\u0026nbsp;hence matching\u0026nbsp;the classical result of Shapley (1974), which was based on the Lemke-Howson algorithm and shows\u0026nbsp;a similar fact about Nash\u0026nbsp;equilibria of a 2-person bimatrix game.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;(This is joint work with Jugal Garg, Milind Sohoni and Vijay V. Vazirani.)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Lemke-Type Algorithm for Market Equilibrium Under Separable, Piecewise-Linear Concave Utilities"}],"uid":"27263","created_gmt":"2011-11-04 10:49:16","changed_gmt":"2016-10-08 01:56:32","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-12-01T15:30:00-05:00","event_time_end":"2011-12-01T15:30:00-05:00","event_time_end_last":"2011-12-01T15:30:00-05:00","gmt_time_start":"2011-12-01 20:30:00","gmt_time_end":"2011-12-01 20:30:00","gmt_time_end_last":"2011-12-01 20:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"72306":{"#nid":"72306","#data":{"type":"event","title":"ARC Colloquium: Andrey Kupavskii, Yandex Corporate","body":"","field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"On r-colorability of random hypergraphs"}],"uid":"27263","created_gmt":"2011-11-02 12:20:15","changed_gmt":"2016-10-08 01:56:32","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-11-14T12:30:00-05:00","event_time_end":"2011-11-14T12:30:00-05:00","event_time_end_last":"2011-11-14T12:30:00-05:00","gmt_time_start":"2011-11-14 17:30:00","gmt_time_end":"2011-11-14 17:30:00","gmt_time_end_last":"2011-11-14 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"71802":{"#nid":"71802","#data":{"type":"event","title":"ARC Theory Day","body":[{"value":"\u003Cp\u003EARC Theory Day will be an annual event, to showcase lectures on recent exciting developments in theoretical computer science. This year\u0027s inaugural event features four young speakers who have made such valuable contributions to the field. In addition, this year we are fortunate to have Avi Wigderson from the Institute for Advanced Study (Princeton) speak on fundamental questions and progress in computational complexity to a general audience.\u003C\/p\u003E\u003Cp\u003EProgram\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003E9:20 AM\u0026nbsp; Welcome by Zvi Galil\u003C\/li\u003E\u003Cli\u003E9:30 AM\u0026nbsp; Thomas Dueholm Hansen -\u003Ca href=\u0022http:\/\/hdl.handle.net\/1853\/42026%20\u0022\u003E Subexponential Lower Bounds For Randomized\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Pivoting Rules For The Simplex Algorithm\u0026nbsp;\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003E10:45 AM\u0026nbsp; Aleksander Madry - \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/42027\u0022\u003EOnline Algorithms and The K-server Conjecture\u0026nbsp;\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003E1:30 PM\u0026nbsp; Mohit Singh - \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/42028\u0022\u003EA Randomized Rounding Approach for Symmetric TSP\u0026nbsp;\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003E2:45 PM\u0026nbsp; Ryan Williams - \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/42029\u0022\u003EAlgorithms for Circuits and Circuits for Algorithms\u0026nbsp;\u003C\/a\u003E\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003ESee \u003Ca href=\u0022http:\/\/hg.gatech.edu\/sites\/default\/files\/arc_theory_day_poster_2.pdf\u0022\u003EPoster\u003C\/a\u003E for schedule of talks.\u003C\/p\u003E\u003Cp\u003ESee ARC \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/45036\u0022\u003ETheory Day Videos\u003C\/a\u003E here.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2011-10-25 12:34:20","changed_gmt":"2016-10-08 01:56:28","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-11-11T08:15:00-05:00","event_time_end":"2011-11-11T15:00:00-05:00","event_time_end_last":"2011-11-11T15:00:00-05:00","gmt_time_start":"2011-11-11 13:15:00","gmt_time_end":"2011-11-11 20:00:00","gmt_time_end_last":"2011-11-11 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali, Director of ARC.\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"72597":{"#nid":"72597","#data":{"type":"event","title":"Joint ARC and School of Math Colloquium by Avi Wigderson, Institute for Advanced Study, Princeton","body":[{"value":"\u003Cp\u003ETitle: The power and weakness of randomness (when you are short on time)\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EMan has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I\u0027ll describe two main aspects of this research on randomness, demonstrating respectively its power and weakness for making algorithms faster. I will address the role of randomness in other computational settings, such as space bounded computation and probabilistic and zero-knowledge proofs.\u003C\/p\u003E\u003Cp\u003EThis is a joint ARC-SoM colloquium, and is in conjunction with the ARC Theory Day on November 11, 2011\u003C\/p\u003E\u003Cp\u003E4:30 pm - Klaus 1116 E \u0026amp; W\u003C\/p\u003E\u003Cp\u003ETitle: Local correction of codes and Euclidean Incidence Geometry\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EA classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem, which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of algebraic and analytic tools.\u003C\/p\u003E\u003Cp\u003EJoint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff\u003C\/p\u003E\u003Cp\u003EAvi Wigderson Lecture \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/42025\u0022\u003EVideo\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":"The power and weakness of randomness (when you are short on time)"}],"uid":"27263","created_gmt":"2011-11-10 09:05:27","changed_gmt":"2016-10-08 01:56:37","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-11-10T10:00:00-05:00","event_time_end":"2011-11-10T10:00:00-05:00","event_time_end_last":"2011-11-10T10:00:00-05:00","gmt_time_start":"2011-11-10 15:00:00","gmt_time_end":"2011-11-10 15:00:00","gmt_time_end_last":"2011-11-10 15:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali, Director of ARC\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"71571":{"#nid":"71571","#data":{"type":"event","title":"ARC Colloquium: Vitaly Feldman, IBM Research - Almaden","body":[{"value":"\u003Cp\u003E\u0026nbsp;Abstract:\u003C\/p\u003E\u003Cp\u003EStatistical query (SQ) learning (Kearns, 1993) model is a restriction of Valiant\u0027s learning model (1984) that models learning from statistical properties of examples rather than from individual examples. Almost all known learning algorithms can be expressed using statistical queries making the SQ complexity of learning useful in understanding the complexity of learning in general. In addition, SQ learning is closely related to Valiant\u0027s (2006) model of evolvability where evolution is modeled as a learning process.\u003C\/p\u003E\u003Cp\u003EIn this talk I will give an overview of the techniques for characterizing and evaluating the SQ complexity of learning and describe two recent applications of these techniques to evolvability. The first application resolves the question of whether Boolean conjunctions are evolvable distribution-independently. The second application gives a simple algorithm for evolving linear threshold functions.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EStatistical query (SQ) learning (Kearns, 1993) model is a restriction of Valiant\u0027s learning model (1984) that models learning from statistical properties of examples rather than from individual examples.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Bounds on complexity of SQ learning and evolvability"}],"uid":"27263","created_gmt":"2011-10-19 14:04:00","changed_gmt":"2016-10-08 01:56:24","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-11-07T12:30:00-05:00","event_time_end":"2011-11-07T12:30:00-05:00","event_time_end_last":"2011-11-07T12:30:00-05:00","gmt_time_start":"2011-11-07 17:30:00","gmt_time_end":"2011-11-07 17:30:00","gmt_time_end_last":"2011-11-07 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"14810","name":"learning algorithms"},{"id":"167581","name":"Statistical query (SQ)"},{"id":"14809","name":"Valiant\u0027s"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"71294":{"#nid":"71294","#data":{"type":"event","title":"ARC Colloquium: David Pritchard, NSERC","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EThis is a talk in two parts, linked by probabilistic methods and linear algebra. In the first half, we look at the problem of finding all 2-edge cuts in a graph. For this we give a simple algorithm based on uniformly sampling the graph\u0027s cycle space (all Eulerian subgraphs). Its distributed implementation is time-optimal on every graph. In the second half, we talk about partitioning set systems into set covers. Mainly, as a function of the minimum degree and maximum set size, how many disjoint covers can be obtained? The tools used to answer this include discrepancy theory and iterated linear programming.\u003C\/p\u003E\u003Cp\u003EThis is joint work with R. Thurimella; and with B. Bollobas, T. Rothvoss, \u0026amp; A. Scott.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EThis is a talk in two parts, linked by probabilistic methods and linear algebra.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Randomized Algorithms for Cuts and Colourings"}],"uid":"27263","created_gmt":"2011-10-14 15:07:38","changed_gmt":"2016-10-08 01:56:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-10-31T14:30:00-04:00","event_time_end":"2011-10-31T14:30:00-04:00","event_time_end_last":"2011-10-31T14:30:00-04:00","gmt_time_start":"2011-10-31 18:30:00","gmt_time_end":"2011-10-31 18:30:00","gmt_time_end_last":"2011-10-31 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"14737","name":"\u0026 A. Scott."},{"id":"14734","name":"graph\u0027s cycle space"},{"id":"14733","name":"linear algebra"},{"id":"14735","name":"R. Thurimella; and with B. Bollobas"},{"id":"14736","name":"T. Rothvoss"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali\u003Cbr \/\u003EDirector, Algorithms Research Center\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"71768":{"#nid":"71768","#data":{"type":"event","title":"ARC Colloquium: Nick Harvey, University of British Columbia, CA","body":"","field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Title: Graph Sparsifiers: A Survey"}],"uid":"27263","created_gmt":"2011-10-24 14:28:20","changed_gmt":"2016-10-08 01:56:28","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-10-26T14:30:00-04:00","event_time_end":"2011-10-26T14:30:00-04:00","event_time_end_last":"2011-10-26T14:30:00-04:00","gmt_time_start":"2011-10-26 18:30:00","gmt_time_end":"2011-10-26 18:30:00","gmt_time_end_last":"2011-10-26 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"71285":{"#nid":"71285","#data":{"type":"event","title":"ARC Colloquium: Ola Svensson,  \u00c9cole polytechnique f\u00e9d\u00e9rale de Lausanne EPFL","body":[{"value":"\u003Cp\u003E\u003Cbr \/\u003EWe present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost.\u003C\/p\u003E\u003Cp\u003EFor the TSP on graphic metrics (graph-TSP), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4\/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.\u003C\/p\u003E\u003Cp\u003EThis is joint work with Tobias Momke.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003E\u003Cbr \/\u003EWe present a framework for approximating the metric TSP based on a novel use of matchings.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Approximating Graphic TSP by Matchings"}],"uid":"27263","created_gmt":"2011-10-14 11:39:40","changed_gmt":"2016-10-08 01:56:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-10-19T14:30:00-04:00","event_time_end":"2011-10-19T14:30:00-04:00","event_time_end_last":"2011-10-19T14:30:00-04:00","gmt_time_start":"2011-10-19 18:30:00","gmt_time_end":"2011-10-19 18:30:00","gmt_time_end_last":"2011-10-19 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"14722","name":"approximation algorithm"},{"id":"14724","name":"claw-free graphs"},{"id":"14721","name":"graph-TSP"},{"id":"14723","name":"Held-Karp"},{"id":"14725","name":"traveling salesman path"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali\u003Cbr \/\u003EDirector, Algorithms Research Center\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"71292":{"#nid":"71292","#data":{"type":"event","title":"ARC Colloquium: Shang-Hua Teng, University of Southern California","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EWe describe an emerging paradigm, which we refer to as the Laplacian Paradigm, for the design of efficient algorithms for massive graphs. This paradigm is built on a recent collection of nearly-linear-time primitives in Spectral Graph Theory developed by Spielman and Teng. Their key primitive is a solver for a linear system, Ax = b, where A is the Laplacian matrix of a weighted, undirected n-vertex graph and b is an n-dimensional vector. Other primitives include nearly-linear-time algorithms for local clustering, spectral sparsification, and low stretch spanning trees. When applying the Laplacian Paradigm, we reduce the input problem to one or multiple problems that can be efficiently solved by these spectral primitives.\u003C\/p\u003E\u003Cp\u003EThe Laplacian Paradigm has been used in a recent algorithm for computing an approximately maximum s-t flow in an undirected graph. This flow is computed by solving a sequence of electrical flow problems. Each electrical flow is given by the solution of a system of linear equations in a Laplacian matrix, and thus may be approximately computed in nearly-linear time. Using this approach, we develop the fastest known algorithm for computing approximately maximum s-t flows as well as the fastest known algorithm for approximating minimum s-t cut in a graph. The Laplacian paradigm has also been applied to obtain nearly-linear-time algorithms for applications in semi-supervised learning, image process, web-spam detection, eigenvalue approximation, and for solving elliptic finite element systems.\u003C\/p\u003E\u003Cp\u003ERecently, almost all original primitives in this collection including the Laplacian solver itself have been significantly improved. Practical implementation might become available in the near future. The goal of this presentation is to encourage more researchers to consider the use of the Laplacian Paradigm to develop faster algorithms for solving fundamental problems in combinatorial optimization, scientific computing, machine learning, network analysis, and other applications that involve massive graphs.\u003C\/p\u003E\u003Cp\u003EJoint work with Daniel Spielman (Yale) and Paul Christiano (MIT), Jonathan Kelner (MIT), and Aleksander Madry (MIT).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003E\u003Cbr \/\u003EWe describe an emerging paradigm, which we refer to as the Laplacian Paradigm, for the design of efficient algorithms for massive graphs.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"The Laplacian Paradigm: Emerging Algorithms for Massive Graphs"}],"uid":"27263","created_gmt":"2011-10-14 11:52:09","changed_gmt":"2016-10-08 01:56:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-10-03T14:30:00-04:00","event_time_end":"2011-10-03T14:30:00-04:00","event_time_end_last":"2011-10-03T14:30:00-04:00","gmt_time_start":"2011-10-03 18:30:00","gmt_time_end":"2011-10-03 18:30:00","gmt_time_end_last":"2011-10-03 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"14732","name":"Aleksander Madry (MIT)."},{"id":"14727","name":"algorithms for massive graphs"},{"id":"14729","name":"Daniel Spielman (Yale)"},{"id":"14731","name":"Jonathan Kelner (MIT)"},{"id":"14726","name":"Laplacian Paradigm"},{"id":"14730","name":"Paul Christiano (MIT)"},{"id":"167580","name":"Spielman and Teng"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EPrasad Tetali\u003Cbr \/\u003EDirector, Algorithms Research Center\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"70197":{"#nid":"70197","#data":{"type":"event","title":"ARC Colloquium: Frank Vallentin, Delft Institute of Applied Mathematics","body":"","field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"New applications of semidefinite programming: Discrete geometry and harmonic analysis"}],"uid":"27263","created_gmt":"2011-09-23 11:02:41","changed_gmt":"2016-10-08 01:55:50","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-09-26T14:30:00-04:00","event_time_end":"2011-09-26T14:30:00-04:00","event_time_end_last":"2011-09-26T14:30:00-04:00","gmt_time_start":"2011-09-26 18:30:00","gmt_time_end":"2011-09-26 18:30:00","gmt_time_end_last":"2011-09-26 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"69774":{"#nid":"69774","#data":{"type":"event","title":"ARC Colloquium: Dieter van Melkebeek, University of Wisconsin - Madison","body":"","field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses"}],"uid":"27263","created_gmt":"2011-09-02 08:12:41","changed_gmt":"2016-10-08 01:53:20","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2011-09-19T14:30:00-04:00","event_time_end":"2011-09-19T14:30:00-04:00","event_time_end_last":"2011-09-19T14:30:00-04:00","gmt_time_start":"2011-09-19 18:30:00","gmt_time_end":"2011-09-19 18:30:00","gmt_time_end_last":"2011-09-19 18:30: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":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}