{"349151":{"#nid":"349151","#data":{"type":"event","title":"ARC Colloquium: Brittany Terese Fasy\u2013Tulane University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003E(Note: location changed to CCB 102)\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003E Providing Statistical Guarantees for Topological Summaries of Data\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003Cbr \/\u003EPersistent homology is a method for probing topological properties of point clouds and function. The method involves tracking the birth and death of topological features as one varies a tuning parameter. Features with short lifetimes are informally considered to be \u201ctopological noise.\u201d I am interested in bringing statistical ideas to persistent homology in order to distinguish topological signal from topological noise and to derive meaningful, yet computable, summaries of large datasets.\u0026nbsp; In this talk, I will define some of the existing topological summaries of data, and show how we can provide statistical guarantees of these summaries.\u003Cbr \/\u003E\u003Ca href=\u0022http:\/\/www.fasy.us\u0022 target=\u0022_blank\u0022\u003Ewww.fasy.us\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Providing Statistical Guarantees for Topological Summaries of Data"}],"uid":"27466","created_gmt":"2014-11-25 19:04:53","changed_gmt":"2017-04-13 21:21:01","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-12-08T12:00:00-05:00","event_time_end":"2014-12-08T12:00:00-05:00","event_time_end_last":"2014-12-08T12:00:00-05:00","gmt_time_start":"2014-12-08 17:00:00","gmt_time_end":"2014-12-08 17:00:00","gmt_time_end_last":"2014-12-08 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"hg_media":{"350171":{"id":"350171","type":"image","title":"Brittany Terese Fasy","body":null,"created":"1449245702","gmt_created":"2015-12-04 16:15:02","changed":"1475895075","gmt_changed":"2016-10-08 02:51:15","alt":"Brittany Terese Fasy","file":{"fid":"201081","name":"brittany-fasy.jpg","image_path":"\/sites\/default\/files\/images\/brittany-fasy_0.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/brittany-fasy_0.jpg","mime":"image\/jpeg","size":117529,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/brittany-fasy_0.jpg?itok=BSz8iqFd"}}},"media_ids":["350171"],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"5660","name":"algorithms"},{"id":"438","name":"data"},{"id":"111251","name":"Guarantees"},{"id":"4584","name":"randomness"},{"id":"168002","name":"Statistical"},{"id":"111261","name":"Topological"}],"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\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":""}},"347901":{"#nid":"347901","#data":{"type":"event","title":"ARC Colloquium and ACO Student Seminar: Umesh Vazirani - U. C. Berkeley","body":[{"value":"\u003Cp\u003ETitle:\u003Cbr \/\u003EHow \u201cQuantum\u201d is the D-Wave Machine?\u003Cbr \/\u003E\u003Cbr \/\u003EAbstract:\u003Cbr \/\u003EA special purpose \u0022quantum computer\u0022 manufactured by the Canadian company D-Wave has led to intense excitement in the mainstream media (including a Time magazine cover dubbing it \u0022the infinity machine\u0022) and the computer industry, and a lively debate in the academic community. Scientifically it leads to the interesting question of whether it is possible to obtain quantum effects on a large scale with qubits that are not individually well protected from decoherence. \u003Cbr \/\u003E\u003Cbr \/\u003EWe propose a simple and natural classical model for the D-Wave machine - replacing their superconducting qubits with classical magnets, coupled with nearest neighbor interactions whose strength is taken from D-Wave\u0027s specifications. The behavior of this classical model agrees remarkably well with posted experimental data about the input-output behavior of the D-Wave machine. \u003Cbr \/\u003E\u003Cbr \/\u003EFurther investigation of our classical model shows that despite its simplicity, it exhibits novel algorithmic properties. Its behavior is fundamentally different from that of its close cousin, classical heuristic simulated annealing. In particular, the major motivation behind the D-Wave machine was the hope that it would tunnel through local minima in the energy landscape, minima that simulated annealing got stuck in. The reproduction of D-Wave\u0027s behavior by our classical model demonstrates that tunneling on a large scale may be a more subtle phenomenon than was previously understood. \u003Cbr \/\u003E\u003Cbr \/\u003EIn this talk I will try to make these results accessible to a general computer science audience, as well as discuss future prospects for quantum annealing based quantum computers. \u003Cbr \/\u003E\u003Cbr \/\u003EBased on joint work with Seung Woo Shin, Graheme Smith, and John Smolin.\u003Cbr \/\u003E\u003Cbr \/\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"How \u201cQuantum\u201d is the D-Wave Machine?"}],"uid":"27466","created_gmt":"2014-11-20 17:27:22","changed_gmt":"2017-04-13 21:21:03","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-11-21T12:00:00-05:00","event_time_end":"2014-11-21T13:00:00-05:00","event_time_end_last":"2014-11-21T13:00:00-05:00","gmt_time_start":"2014-11-21 17:00:00","gmt_time_end":"2014-11-21 18:00:00","gmt_time_end_last":"2014-11-21 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":[],"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 edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"344861":{"#nid":"344861","#data":{"type":"event","title":"ARC Colloquium And Machine Learning (ML) Seminar Series with Geoffrey Hinton","body":[{"value":"\u003Cp class=\u0022p1\u0022\u003EAlgorithms \u0026amp; Randomness Center (ARC) Colloquium and Machine Learning (ML) Seminar Series\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003EWednesday, November 19, 2014\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003EKlaus 1116 E \u0026amp; W - 1:30 pm\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003EGeoffrey Hinton \u2013\u0026nbsp;\u003C\/strong\u003E\u003Cstrong\u003EDistinguished Professor, University of Toronto and Distinguished Researcher, Google\u003C\/strong\u003E\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;\u0022Deep Learning\u0022\u0026nbsp;\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003EDr. Hinton will give a brief history of deep learning explaining what it is, what kinds of task it should be good for and why it was largely abandoned in the 1990\u0027s. He will then describe how ideas from statistical physics were used to make deep learning work much better on small datasets. Finally Dr. Hinton will describe how deep learning is now used by Google for speech recognition and object recognition and how it may soon\u0026nbsp; be used for machine translation.\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp class=\u0022p1\u0022\u003EGeoffrey Hinton received his BA in experimental psychology from Cambridge in 1970 and his PhD in Artificial Intelligence from Edinburgh in 1978. He did postdoctoral work at Sussex University and the University of California San Diego and spent five years as a faculty member in the Computer Science department at Carnegie-Mellon University. He then became a fellow of the Canadian Institute for Advanced Research and moved to the Department of Computer Science at the University of Toronto. He spent three years from 1998 until 2001 setting up the Gatsby Computational Neuroscience Unit at University College London and then returned to the University of Toronto where he is a University Professor. He is the director of the program on \u0022Neural Computation and Adaptive Perception\u0022 which is funded by the Canadian Institute for Advanced Research. Geoffrey Hinton is a fellow of the Royal Society, the Royal Society of Canada, and the Association for the Advancement of Artificial Intelligence. He is an honorary foreign member of the American Academy of Arts and Sciences, and a former president of the Cognitive Science Society. He has received honorary doctorates from the University of Edinburgh and the University of Sussex. He was awarded the first David E. Rumelhart prize (2001), the IJCAI award for research excellence (2005), the IEEE Neural Network Pioneer award (1998), the ITAC\/NSERC award for contributions to information technology (1992) the Killam prize for Engineering (2012) and the NSERC Herzberg Gold Medal (2010) which is Canada\u0027s top award in Science and Engineering. Geoffrey Hinton designs machine learning algorithms. His aim is to discover a learning procedure that is efficient at finding complex structure in large, high-dimensional datasets and to show that this is how the brain learns to see. He was one of the researchers who introduced the back-propagation algorithm that has been widely used for practical applications. His other contributions to neural network research include Boltzmann machines, distributed representations, time-delay neural nets, mixtures of experts, variational learning, products of experts and deep belief nets. His current main interest is in unsupervised learning procedures for multi-layer neural networks with rich sensory input.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Dr. Geoffrey Hinton, Distinguished Professor at the University of Toronto and Distinguished Researcher for Google, will present a video seminar on the history of deep learning."}],"uid":"27998","created_gmt":"2014-11-12 14:05:38","changed_gmt":"2016-10-08 02:10:18","author":"Brittany Aiello","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-11-19T12:30:00-05:00","event_time_end":"2014-11-19T13:30:00-05:00","event_time_end_last":"2014-11-19T13:30:00-05:00","gmt_time_start":"2014-11-19 17:30:00","gmt_time_end":"2014-11-19 18:30:00","gmt_time_end_last":"2014-11-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":"50876","name":"School of Interactive Computing"},{"id":"50877","name":"School of Computational Science and Engineering"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"12781","name":"algorithms \u0026 randomness center"},{"id":"4265","name":"ARC"},{"id":"109581","name":"deep learning"},{"id":"109571","name":"Geoffrey Hinton"},{"id":"9167","name":"machine learning"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003C\/p\u003E\u003Cp\u003EAdministrative Professional III\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022mailto:dani.denton@cc.gatech.edu\u0022\u003Edani.denton@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"344241":{"#nid":"344241","#data":{"type":"event","title":"ARC Colloquium: YinTat Lee - Massachusetts Institute of Technology","body":[{"value":"\u003Cp class=\u0022p1\u0022\u003E\u003Cstrong\u003ETea and light refreshments 2:00 pm in Klaus Room 2222\u003C\/strong\u003E\u003C\/p\u003E\u003Cp class=\u0022p2\u0022\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;\u003Cbr \/\u003E A Faster Algorithm for Linear Programming\u003Cbr \/\u003E \u003Cbr \/\u003E \u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u0026nbsp;\u003Cbr \/\u003E In this talk I will present a new algorithm for solving linear programs. Given a linear program with n variables, m \u0026gt; n constraints, and bit complexity L, our algorithm runs in \u00d5(sqrt(n) L) iterations each consisting of solving \u00d5(1) linear systems and additional nearly linear time computation. Our method improves upon the convergence rate of previous state-of-the-art linear programming methods which required solving either \u00d5(sqrt(m)L) linear systems [R88] or consisted of \u00d5((mn)^(1\/4)) steps of more expensive linear algebra [VA93].\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E Interestingly, our algorithm not only nearly matches the convergence rate of the universal barrier of Nesterov and Nemirovskii [NN94], but in the special case of the linear programming formulation of various flow problems our methods converge at a rate faster than that predicted by any self-concordant barrier. In particular, we achieve a running time of \u00d5(|E| sqrt(|V| log^2 U) for solving the maximum flow problem on a directed graph with |E| edges, |V| vertices, and capacity ratio U, thereby improving upon the previous fastest running time for solving this problem when |E| \u0026gt; \u03a9(|V|^1+epsilon) for any constant epsilon.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E This talk will assume little exposure to linear programming algorithms, convex optimization, or graph theory and will require no previous experience with the universal barrier or self-concordance.\u0026nbsp;\u003Cbr \/\u003E \u003Cbr \/\u003E This talk reflects joint work with Aaron Sidford.\u0026nbsp;\u003Cbr \/\u003E \u0026nbsp;See \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1312.6677\u0022 title=\u0022http:\/\/arxiv.org\/abs\/1312.6677\u0022\u003Ehttp:\/\/arxiv.org\/abs\/1312.6677\u003C\/a\u003E and \u003Ca href=\u0022http:\/\/arxiv.org\/abs\/1312.6713\u0022 title=\u0022http:\/\/arxiv.org\/abs\/1312.6713\u0022\u003Ehttp:\/\/arxiv.org\/abs\/1312.6713\u003C\/a\u003E\u003C\/p\u003E\u003Cp class=\u0022p2\u0022\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003Cbr \/\u003E Yin Tat Lee is a PhD student (under Professor Jonathan Kelner) at MIT, studying theoretical computer science. His areas of research span convex optimization, linear programming, spectral graph theory and algorithmic graph theory. He is particularly interested in combining convex optimization and combinations techniques to design fast algorithms for fundamental cut\/flow problems. He is one of the recipients of the Best Paper Awards at SODA 2014, FOCS 2014 for his results on the maximum flow problem and linear programming.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Faster Algorithm for Linear Programming"}],"uid":"27998","created_gmt":"2014-11-11 10:20:13","changed_gmt":"2016-10-08 02:07:49","author":"Brittany Aiello","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-11-17T12:00:00-05:00","event_time_end":"2014-11-17T13:00:00-05:00","event_time_end_last":"2014-11-17T13:00:00-05:00","gmt_time_start":"2014-11-17 17:00:00","gmt_time_end":"2014-11-17 18:00:00","gmt_time_end_last":"2014-11-17 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"2924","name":"MIT"},{"id":"109351","name":"Yin Tat Lee"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp class=\u0022p1\u0022\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"340101":{"#nid":"340101","#data":{"type":"event","title":"ARC Colloquium: Siu On Chan - Microsoft Research","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EEfficient Density Estimation via Piecewise Polynomial Approximation\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe give a highly efficient \u0022semi-agnostic\u0022 algorithm for learning univariate probability distributions that are well approximated by piecewise polynomial density functions. Let p be an arbitrary distribution over an interval I which is \u03c4-close (in total variation distance) to an unknown probability distribution q that is defined by an unknown partition of I into t intervals and t unknown degree-d polynomials specifying q over each of the intervals. We give an algorithm that draws O~(t (d+1)\/\u03b5^2) samples from p, runs in time poly(t,d,1\/ \u03b5), and with high probability outputs a piecewise polynomial hypothesis distribution h that is (O(\u03c4)+\u03b5)-close (in total variation distance) to p. This sample complexity is essentially optimal; we show that even for \u03c4=0, any algorithm that learns an unknown t-piecewise degree-d probability distribution over I to accuracy \u03b5 must use \u03a9(t(d+1)\/(polylog(d+1) \u03b5^2)) samples from the distribution, regardless of its running time. Our algorithm combines tools from approximation theory, uniform convergence, linear programming, and dynamic programming.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EWe apply this general algorithm to obtain a wide range of results for many natural problems in density estimation over both continuous and discrete domains. These include state-of-the-art results for learning mixtures of log-concave distributions; mixtures of t-modal distributions; mixtures of Monotone Hazard Rate distributions; mixtures of Poisson Binomial Distributions; mixtures of Gaussians; and mixtures of k-monotone densities. Our general technique yields computationally efficient algorithms for all these problems, in many cases with provably optimal sample complexities (up to logarithmic factors) in all parameters.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EShort Bio:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESiu On Chan is a Postdoc at Microsoft Research. He did his undergrad in Chinese University of Hong Kong, MSc at University of Toronto, and PhD at UC Berkeley. He is interested in studying the limitations of approximation algorithms, in terms of NP-hardness and integrality gaps of convex programming hierarchies. He is also interested in random graphs and property testing. He received a Best Paper Award at STOC 2013.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Efficient Density Estimation via Piecewise Polynomial Approximation"}],"uid":"27466","created_gmt":"2014-11-03 17:42:36","changed_gmt":"2017-04-13 21:21:17","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-11-10T12:00:00-05:00","event_time_end":"2014-11-10T12:00:00-05:00","event_time_end_last":"2014-11-10T12:00:00-05:00","gmt_time_start":"2014-11-10 17:00:00","gmt_time_end":"2014-11-10 17:00:00","gmt_time_end_last":"2014-11-10 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":[],"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":""}},"336011":{"#nid":"336011","#data":{"type":"event","title":"ARC Colloquium: Bartosz Walczak - School of Mathematics, Georgia Tech","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EOn-line Approach to Off-line Graph Coloring Problems\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe on-line graph coloring problem is modeled by a game between two players: Presenter, who constructs a graph of some fixed class presenting new vertices one by one, and Algorithm, who colors each vertex right after it is presented without the possibility of changing the color afterwards. The goal of Algorithm is to use as few colors as possible, while Presenter tries to force Algorithm to use many colors. Any game of this kind gives rise to a new class of graphs, called game graphs, which \u0022encode\u0022 strategies of Presenter in the game. The chromatic number of such a game graph is equal to the number of colors that Algorithm is forced to use playing against the corresponding strategy. It turns out that game graphs of appropriately defined games can be modeled as intersection graphs of geometric objects. This is the key idea which combined with on-line competitivity analysis and graph decomposition techniques yields lower and upper bounds on the maximum possible chromatic number in various classes of geometric intersection graphs. I will survey results obtained with this method, present in detail its application to constructing triangle-free geometric intersection graphs with arbitrarily large chromatic number (solution to a problem of Erd\u0151s from the 1970s), and discuss several open problems that arose from this research. This is my joint work with various coauthors during last 2 years.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EARC:\u003C\/strong\u003E \u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/\u0022\u003Ehttp:\/\/www.arc.gatech.edu\/\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"On-line Approach to Off-line Graph Coloring Problems"}],"uid":"27466","created_gmt":"2014-10-21 17:29:45","changed_gmt":"2017-04-13 21:21:22","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-10-27T14:00:00-04:00","event_time_end":"2014-10-27T15:00:00-04:00","event_time_end_last":"2014-10-27T15:00:00-04:00","gmt_time_start":"2014-10-27 18:00:00","gmt_time_end":"2014-10-27 19:00:00","gmt_time_end_last":"2014-10-27 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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":""}},"332001":{"#nid":"332001","#data":{"type":"event","title":"ARC Colloquium: Dick Lipton - School of Computer Science, Georgia Tech","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Knuth Prize Lecture: The Stories Behind the Results\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EI will present a number of stories about some results that I think highlight how results get proved and how they do not. These will span problems from almost all areas of theory, and will include both successes and failures. I hope that beyond the actual results you will enjoy and hopefully profit from the stories.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Knuth Prize Lecture: The Stories Behind the Results"}],"uid":"27263","created_gmt":"2014-10-07 15:38:06","changed_gmt":"2016-10-08 02:09:42","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-10-15T14:00:00-04:00","event_time_end":"2014-10-15T14:00:00-04:00","event_time_end_last":"2014-10-15T14:00:00-04:00","gmt_time_start":"2014-10-15 18:00:00","gmt_time_end":"2014-10-15 18:00:00","gmt_time_end_last":"2014-10-15 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":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\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":""}},"284811":{"#nid":"284811","#data":{"type":"event","title":"ARC Colloquium: Gopal Pandurangan - Brown University (RI) and NTU, Singapore","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003EDistributed Algorithmic Foundations of Dynamic Networks\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMany of today\u0027s real-world communication networks are highly dynamic, i.e., their network topology changes continuously over time. Examples include Peer-to-Peer (P2P) networks and ad hoc wireless and sensor networks. Such networks are now widely used in various applications, including sharing data and resources, search and storage, Internet telephony, environment monitoring and management. In P2P networks (e.g., Skype, BitTorrent), the topology changes at a rapid rate due to continuous joining and leaving of nodes; in ad hoc sensor and vehicular networks, the topology changes dynamically due to failure or mobility of the nodes. Performing robust and efficient non-trivial distributed computation in such highly dynamic networks is challenging. In this\u0026nbsp;talk, I will give an overview of our recent results that make progress towards developing an algorithmic theory of dynamic networks. First, I will present a rigorous theoretical framework for studying dynamic networks. Then I will present efficient techniques and algorithms for solving the fundamental agreement problem in dynamic networks. I will also present efficient algorithms for key problems such as information spreading, search, and storage. To complement our algorithms, I will also present almost tight lower bounds for agreement and information spreading.\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Distributed Algorithmic Foundations of Dynamic Networks"}],"uid":"27263","created_gmt":"2014-03-24 07:48:41","changed_gmt":"2017-04-13 21:22:52","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-04-28T18:30:00-04:00","event_time_end":"2014-04-28T18:30:00-04:00","event_time_end_last":"2014-04-28T18:30:00-04:00","gmt_time_start":"2014-04-28 22:30:00","gmt_time_end":"2014-04-28 22:30:00","gmt_time_end_last":"2014-04-28 22: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":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"290061":{"#nid":"290061","#data":{"type":"event","title":"ARC Colloquium: Howard Karloff - Yahoo Labs","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: Maximum Entropy Summary Trees\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EGiven a very large, node-weighted, rooted tree on, say, n nodes, if one has only enough space to display a k-node summary of the tree, what is the most informative way to draw the tree?\u0026nbsp; We define a type of weighted tree that we call a \u0022summary tree\u0022 of the original tree, that results from aggregating nodes of the original tree subject to certain constraints. We suggest that the best choice of which summary tree to use (among those with a fixed number of nodes) is the one that maximizes the information-theoretic entropy of a natural probability distribution associated with the summary tree, and we provide a (pseudopolynomial-time) dynamic-programming algorithm to compute this maximum entropy summary tree, when the weights are integral. The result is an automated way to summarize large trees and retain as much information about them as possible, while using (and displaying) only a fraction of the original node set.\u0026nbsp; We also provide an additive approximation algorithm and a greedy heuristic that are faster than the optimal algorithm, and generalize to trees with real-valued weights.\u003C\/p\u003E\u003Cp\u003EThis is joint work with Ken Shirley of ATT Labs and Richard Cole of NYU.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Maximum Entropy Summary Trees"}],"uid":"27263","created_gmt":"2014-04-11 10:27:21","changed_gmt":"2017-04-13 21:22:44","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-04-24T16:00:00-04:00","event_time_end":"2014-04-24T16:00:00-04:00","event_time_end_last":"2014-04-24T16:00:00-04:00","gmt_time_start":"2014-04-24 20:00:00","gmt_time_end":"2014-04-24 20:00:00","gmt_time_end_last":"2014-04-24 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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"284621":{"#nid":"284621","#data":{"type":"event","title":"ARC Seminar\/DOS: Samuel Fiorini - Universit\u00e9 libre de Brussels (Brussels, Belgium).","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Cut-dominant and forbidden minors\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe cut-dominant of a connected graph G is the polyhedron that corresponds to the problem of computing global min-cuts in G. Despite the fact that computing a global min-cut can be done in polynomial time, the geometry of the cut-dominant is far from being understood. We study graphs for which all facets of the corresponding cut-dominant have right-hand side at most a fixed integer k. These graphs form a minor-closed collection. We give a complete list of forbidden minors for k \u0026lt;= 2. This is then applied to the TSP to give a shorter proof of a classic result of Fonlupt and Naddef (Math. Prog., 1992) \u0026nbsp;that characterizes TSP-perfect graphs. This work in progress is joint with Kanstantsin Pashkovich (Brussels) and Michele Conforti (Padova).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Samuel Fiorini will give a talk at the ARC Seminar"}],"uid":"27263","created_gmt":"2014-03-21 08:33:01","changed_gmt":"2017-04-13 21:22:54","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-26T17:00:00-04:00","event_time_end":"2014-03-26T18:00:00-04:00","event_time_end_last":"2014-03-26T18:00:00-04:00","gmt_time_start":"2014-03-26 21:00:00","gmt_time_end":"2014-03-26 22:00:00","gmt_time_end_last":"2014-03-26 22: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":"6121","name":"DOS"},{"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":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:sebastian.pokutta@isye.gatech.edu\u0022\u003Esebastian.pokutta@isye.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"283031":{"#nid":"283031","#data":{"type":"event","title":"ARC Colloquium: Atri Rudra - University at Buffalo, SUNY","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E A Tale of Two Join Algorithms\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn this talk we will talk about two new database join algorithms with provable optimality guarantees.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;We first present a recent algorithm (PODS 2012) that is the first provably optimal (worst-case) algorithm to compute database joins. As a special case, this join algorithm implies (i) The first algorithmic versions of some well-known geometric inequalities due to Loomis and Whitney (and their generalizations by Bollobas and Thomason); (ii) Algorithmically list recoverable codes that work with parameters that no known algorithmic list recovery result work with (e.g. those based on the Reed-Solomon codes) and an application of this result in designing sublinear time decodable compressed sensing schemes; (ii) Worst-case optimal algorithm to list all occurrences of any fixed hypergraph H in a given large hypergraph G.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The second algorithm (PODS 2014) has stronger optimality guarantees: we present an adaptive join algorithm whose run time depends on the \u0022difficulty\u0022 of the data. We believe that this algorithm has more practical applications since worst-case optimal algorithms might have terrible performance on \u0022real data.\u0022 As a special case, we present an (almost) instance optimal algorithm (with respect to comparison based algorithms) for a large class of join queries (namely Fagin\u0027s \\beta-acyclic queries).\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The talk will be self-contained and is based on join(t) works with Ngo, Nguyen, Porat and Re.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Tale of Two Join Algorithms"}],"uid":"27263","created_gmt":"2014-03-13 11:08:18","changed_gmt":"2017-04-13 21:22:56","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-24T18:30:00-04:00","event_time_end":"2014-03-24T18:30:00-04:00","event_time_end_last":"2014-03-24T18:30:00-04:00","gmt_time_start":"2014-03-24 22:30:00","gmt_time_end":"2014-03-24 22:30:00","gmt_time_end_last":"2014-03-24 22:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"277141":{"#nid":"277141","#data":{"type":"event","title":"ARC Colloquium: Michael O. Rabin, Harvard University, Columbia University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Electronic Voting Using The\u0026nbsp; Split Value Representation\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe present an e-voting system wherein votes are represented to the vote-tallying center in the form COM(X) = (COM(u) , COM(v)) , vote = val(X) = (u + v) mod p. The voter gets a paper receipt for COM(X). His actual vote remains secret and he cannot be coerced to cast a specified vote. Vote tallying retains secrecy of individual votes while producing and posting a publicly verifiable proof of correctness of announced election results. The presentation will be generally accessible. Joint work with Ron Rivest.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Electronic Voting using the Split Value Representation"}],"uid":"27263","created_gmt":"2014-02-18 13:35:38","changed_gmt":"2017-04-13 21:23:08","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-11T16:00:00-04:00","event_time_end":"2014-03-11T17:00:00-04:00","event_time_end_last":"2014-03-11T17:00:00-04:00","gmt_time_start":"2014-03-11 20:00:00","gmt_time_end":"2014-03-11 21:00:00","gmt_time_end_last":"2014-03-11 21: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":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"277121":{"#nid":"277121","#data":{"type":"event","title":"ARC Colloquium: Michael O. Rabin, Harvard University, Columbia University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;Practically Efficient ZKPs for Preventing Collusion in Auctions\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn an important mechanism for sealed bid auctions developed by Vickrey and rewarded by a Nobel Prize, the highest bidder gets the item and pays the second highest bid value. Vickrey proved that for these auctions the best strategy for a participant is to bid his private true value for the item. Despite this advantage, second-price auctions are rarely used because they are subject to collusion of bidders. Employing novel cryptography we show that collusion can be avoided thus solving a long standing open problem. The talk will be generally accessible. Joint work with Silvio Micali.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Practically Efficient ZKPs for Preventing Collusion in Auctions"}],"uid":"27263","created_gmt":"2014-02-18 13:26:15","changed_gmt":"2017-04-13 21:23:08","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-10T16:30:00-04:00","event_time_end":"2014-03-10T17:30:00-04:00","event_time_end_last":"2014-03-10T17:30:00-04:00","gmt_time_start":"2014-03-10 20:30:00","gmt_time_end":"2014-03-10 21:30:00","gmt_time_end_last":"2014-03-10 21: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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"278451":{"#nid":"278451","#data":{"type":"event","title":"ARC Colloquium: Grigory Yaroslavtsev, Brown University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Big Data Theory and Randomized Algorithms\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAdvances in machine learning and developments in modern massive parallel computational systems motivate a large number of challenging questions for the theory of computing. How to make sense of massive amounts of noisy data? How to cluster billions of points and compare large images? How to design scalable algorithms for distributed systems?\u003C\/p\u003E\u003Cp\u003EI will present examples of settings in which these questions can be addressed through the design of randomized algorithms:\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003ESublinear algorithms for testing properties of high-dimensional noisy data such (e.g. monotonicity, the Lipschitz property and convexity)\u003C\/li\u003E\u003Cli\u003EDistributed algorithms for geometric problems in Euclidean space (minimum cost spanning tree, Earth-Mover Distance)\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003EThrough these examples I will illustrate how information-theoretic measures of performance such as query complexity and the number of rounds of communication play a key role in the design and analysis of such algorithms. I will show that even in the worst-case these fundamental problems can be solved almost optimally with respect to these measures. The information-theoretic nature is crucial here since lower bounds can be proved unconditionally, i.e. with no computational hardness assumptions.\u003C\/p\u003E\u003Cp\u003EThis talk will be primarily based on two papers which will appear in STOC\u201914 (joint work with Andoni, Berman, Nikolov, Onak and Raskhodnikova) as well as other work by the speaker.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\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":"The Big Data Theory and Randomized Algorithms"}],"uid":"27263","created_gmt":"2014-02-24 13:46:06","changed_gmt":"2017-04-13 21:23:06","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-05T18:00:00-05:00","event_time_end":"2014-03-05T18:00:00-05:00","event_time_end_last":"2014-03-05T18:00:00-05:00","gmt_time_start":"2014-03-05 23:00:00","gmt_time_end":"2014-03-05 23:00:00","gmt_time_end_last":"2014-03-05 23:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"276131":{"#nid":"276131","#data":{"type":"event","title":"ARC Colloquium: Pratik Worah - New York University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: CSPs, Approximation Resistance, and Optimization Hierarchies\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\u003Cp\u003EA k-ary boolean predicate f, naturally implies a canonical constraint satisfaction problem (CSP(f)). Let MAX k-CSP(f) denote the problem of finding the maximum fraction of simultaneously satisfiable constraints in any given instance of CSP(f). A trivial randomized algorithm achieves an approximation factor proportional to f^{-1}(1).\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;On the other hand, it is known, for some f, that an efficient algorithm can not perform strictly better than the trivial algorithm - such f are known as approximation resistant.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;One of the main problems in this area is to characterize which predicates are approximation resistant.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In this talk, I will survey known bounds for CSPs and their connections with LP and SDP hierarchies. Finally, I will give an overview of my recent research in this area, which gives a characterization of approximation resistance.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;(Joint with S.Khot and M.Tulsiani).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"CSPs, Approximation Resistance, and Optimization Hierarchies"}],"uid":"27263","created_gmt":"2014-02-14 16:01:41","changed_gmt":"2017-04-13 21:23:11","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-02-26T12:30:00-05:00","event_time_end":"2014-02-26T12:30:00-05:00","event_time_end_last":"2014-02-26T12:30:00-05:00","gmt_time_start":"2014-02-26 17:30:00","gmt_time_end":"2014-02-26 17:30:00","gmt_time_end_last":"2014-02-26 17: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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"273011":{"#nid":"273011","#data":{"type":"event","title":"ARC Colloquium: CHEUNG Yun Kuen  - New York University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Tatonnement \u0026nbsp;Beyond Gross Substitutes? Gradient Descent to the Rescue\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWalras, while defining the quintessential notion of market equilibrium in 1874, also gave a\u0026nbsp;simple and natural rule for updating prices and called it the tatonnement process. \u0026nbsp;Does the tatonnement process converge to equilibrium prices? This was a central question in mathematical economics for almost a century. Positive news came in the 1950s,\u0026nbsp;when convergence \u0026nbsp;was\u0026nbsp;established for the gross substitutes case. However, it was followed by negative news in the 1960s: an example by Scarf on which tatonnement cycles and the Sonnenschein-Debreu-Mantel theorem which showed that the task was hopeless for a general Arow-Debreu market.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; In this work we have, for the first time, gone beyond the gross substitutes case.\u0026nbsp;We define a class of markets for which tatonnement is equivalent to gradient descent. This is the class of markets for which there is a convex potential function whose gradient is always equal to the negative of the excess demand. We call this class the Convex Potential Function (CPF) markets. We show the following results:\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; - CPF markets contain the class of Eisenberg Gale (EG) markets, defined previously by Jain and Vazirani.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; - The subclass of CPF markets for which the demand is a differentiable function contains exactly those markets whose demand function has a symmetric negative semi-definite Jacobian.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; - We define a family of continuous versions of tatonnement based on gradient descent using a Bregman divergence. As we show, for many CPF markets, every process in this family will converge to an equilibrium and the process based on KL-divergence will converge for even more of these markets. This is analogous to the classic result for markets satisfying the Weak Gross Substitutes property. We use the theory of differential inclusions, a generalization of differential equations, to establish this result.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; - A discrete version of tatonnement converges toward the equilibrium for Fisher markets with buyers having CES or Leontief utility functions; the convergence rates for these settings are analyzed using a common potential function. For the CES case, we prove that the tatonnement converges linearly by showing that the potential function satisfies strong sandwiching property, which is reminiscent of strong convexity.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; I will also discuss our recent results on:\u003C\/p\u003E\u003Cp\u003E\u0026nbsp; - ongoing Fisher markets, a model proposed by Cole and Fleischer. In this model, price updates are asynchronous, and warehouses are incorporated to meet excess demand and store excess supply;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;- Fisher markets with NCES utility functions, a generalization of CES utility functions.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;Joint work with Richard Cole and Nikhil Devanur.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Tatonnement  Beyond Gross Substitutes? Gradient Descent to the Rescue"}],"uid":"27263","created_gmt":"2014-02-03 15:03:04","changed_gmt":"2017-04-13 21:23:16","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-02-24T12:30:00-05:00","event_time_end":"2014-02-24T12:30:00-05:00","event_time_end_last":"2014-02-24T12:30:00-05:00","gmt_time_start":"2014-02-24 17:30:00","gmt_time_end":"2014-02-24 17:30:00","gmt_time_end_last":"2014-02-24 17: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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"272911":{"#nid":"272911","#data":{"type":"event","title":"ARC Colloquium: Marco Molinaro - School of Industrial \u0026 Systems Engineering at Georgia Tech.","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Cstrong\u003EAbstract:\u003C\/strong\u003E A direct sum theorem for two parties and a function f states that the communication cost of solving k copies of f simultaneously with error probability 1\/3 is at least k R_{1\/3}(f), where R_{1\/3}(f) is the communication required to solve a single copy of f with error probability 1\/3. We improve this for a natural family of functions f, showing that the 1-way communication required to solve k copies of f simultaneously with probability 2\/3 is Omega(k R_{1\/k}(f)). Since R_{1\/k}(f) may be as large as Omega(R_{1\/3}(f) log k), we asymptotically beat the direct sum bound for such functions, showing that the trivial upper bound of solving each of the k copies of f with probability 1-O(1\/k) and taking a union bound is optimal! In order to achieve this, our direct sum involves a novel measure of information cost which allows a protocol to abort with constant probability, and otherwise must be correct with very high probability. Moreover, for the functions considered, we show strong lower bounds on the communication cost of protocols with these relaxed guarantees; indeed, our lower bounds match those for protocols that are not allowed to abort.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EIn the distributed and streaming models, where one wants to be correct not only on a single query, but simultaneously on a sequence of n queries, we obtain optimal lower bounds on the communication or space complexity. Lower bounds obtained from our direct sum result show that a number of techniques in the sketching literature are optimal, including the following:\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E- (JL transform) Lower bound of Omega((1\/eps^2) log(n\/delta)) on the dimension of (oblivious) Johnson-Lindenstrauss transforms.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E- (l_p-estimation) Lower bound for the size of encodings of n vectors in [-M, M]^d that allow l_1 or l_2-estimation of Omega((n\/eps^2) log (n\/delta) (log d + log M)).\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E- (Matrix sketching) Lower bound of Omega((1\/eps^2) log n\/delta) on the dimension of a matrix sketch S satisfying the entrywise guarantee |(ASS^TB)_{i,j} - (AB)_{i,j}| \u0026lt;= eps |A_i|_2 |B^j|_2.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E- (Database joins) Lower bound of Omega((n\/eps^2) log(n\/delta) log M) for sketching frequency vectors of n tables in a database, each with M records, in order to allow join size estimation.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EJoint work with David P. Woodruff and Grigory Yaroslavtsev.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching"}],"uid":"27263","created_gmt":"2014-02-03 12:19:43","changed_gmt":"2017-04-13 21:23:16","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-02-17T12:30:00-05:00","event_time_end":"2014-02-17T12:30:00-05:00","event_time_end_last":"2014-02-17T12:30:00-05:00","gmt_time_start":"2014-02-17 17:30:00","gmt_time_end":"2014-02-17 17:30:00","gmt_time_end_last":"2014-02-17 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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"272891":{"#nid":"272891","#data":{"type":"event","title":"ARC Colloquium: Piyush Srivastava - UC Berkeley","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Zeros of polynomials and the computational complexity of\u0026nbsp;problems in statistical physics\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ESpin systems such as the Ising model originated in statistical physics as a tool for the qualitative study of phase transitions in phenomena like magnetism.\u0026nbsp; They have since found applications in the modeling of other complex systems. e.g., in the study of social networks and in machine learning.\u0026nbsp; In this work, we study the computational complexity of computing mean statistics of such models (e.g., the magnetization of the Ising model), and relate these questions to the location of the complex zeros of the \u0022partition function\u0022 (a well studied generating polynomial of the probability distribution specified by such a model).\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E \u003Cbr \/\u003E In two seminal papers, Lee and Yang [1952] initiated the study of the zeros of the partition function, and related phase transitions in the Ising model to the location of such zeros. To use this connection, they then proved the striking theorem that the zeros of the partition function of the so-called \u0022ferromagnetic\u0022 Ising model lie on the unit circle in the complex plane.\u0026nbsp; The study of the location of zeros of other classes of polynomials has an even longer history, and also has applications in probability theory and combinatorics.\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E \u003Cbr \/\u003E In this talk, we will briefly survey the Lee-Yang theorem and its connection to phase transitions, and then present our recent extension of the Lee-Yang theorem which has applications to proving the #P-hardness of computing the magnetization of the Ising model. We will also present another example of our method of using results about locations of zeros of polynomials to prove #P-hardness by applying it to the problem of computing the average size of a matching in the monomer-dimer model.\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E \u003Cbr \/\u003E This talk is based on joint work with Alistair Sinclair.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Zeros of polynomials and the computational complexity of problems in statistical physics"}],"uid":"27263","created_gmt":"2014-02-03 12:16:41","changed_gmt":"2016-10-08 02:06:40","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-02-06T11:30:00-05:00","event_time_end":"2014-02-06T12:30:00-05:00","event_time_end_last":"2014-02-06T12:30:00-05:00","gmt_time_start":"2014-02-06 16:30:00","gmt_time_end":"2014-02-06 17:30:00","gmt_time_end_last":"2014-02-06 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":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78771","name":"Public"}],"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":""}}}