{"168281":{"#nid":"168281","#data":{"type":"event","title":"ARC Colloquium: Sebastian Pokutta, Georgia Tech","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: Extended formulations and complexity of polytopes\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn the first part we will analyze extended formulations of polytopes and we solve a 20-year old problem posed by Yannakakis: there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In view of the aforementioned lower bounds we then turn our attention, in the second part, to approximate extended formulations which approximately project to the desired polytope. We develop a framework for proving approximation limits of polynomial-size linear programs. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1\/2\u2212\u03b5})-approximations for CLIQUE require linear programs of size 2^{n^\u03a9(\u03b5)}. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;This is joint work with G \u0301abor Braun, Samuel Fiorini, Serge Massar, David Steurer, Hans Raj Tiwary, and Ronald de Wolf\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Extended formulations and complexity of polytopes"}],"uid":"27263","created_gmt":"2012-11-05 11:06:27","changed_gmt":"2016-10-08 02:01:06","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-11-26T12:00:00-05:00","event_time_end":"2012-11-26T12:00:00-05:00","event_time_end_last":"2012-11-26T12:00:00-05:00","gmt_time_start":"2012-11-26 17:00:00","gmt_time_end":"2012-11-26 17:00:00","gmt_time_end_last":"2012-11-26 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"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":""}},"158181":{"#nid":"158181","#data":{"type":"event","title":"ARC Colloquium: Pankaj Agarwal, Duke University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Algorithms for Geometric Similarity\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EA basic problem in classifying, or searching for similar objects in, a large set of geometric\u0026nbsp; objects is computing similarity between two objects. This has led to extensive work on computing geometric similarity between two objects. This talk discusses some old and some new geometric algorithms for computing similarity between two point sets, with an emphasis on transportation and Frechet distance. The talk will also touch upon a few open problems in this area.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Algorithms for Geometric Similarity"}],"uid":"27263","created_gmt":"2012-10-01 13:43:32","changed_gmt":"2016-10-08 02:00:10","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-11-19T12:00:00-05:00","event_time_end":"2012-11-19T12:00:00-05:00","event_time_end_last":"2012-11-19T12:00:00-05:00","gmt_time_start":"2012-11-19 17:00:00","gmt_time_end":"2012-11-19 17:00:00","gmt_time_end_last":"2012-11-19 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"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\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"158201":{"#nid":"158201","#data":{"type":"event","title":"ARC-Yandex Workshop: Internet Topology and Economics","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EWorkshop Theme:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe Internet is composed of tens of thousands of interconnected diverse, self-owned smaller networks, called Autonomous Systems (ASes). These ASes engage in strategic decision making to maximize their profits, reliability and performance. The business agreements (e.g. peering and transit) between these ASes play a major role in how the Internet is structured today and how it evolves over time. This important aspect creates a strong connection between networking research, economics and game-theoretic network formation models.\u003C\/p\u003E\u003Cp\u003EThe aim of this workshop is to bring together these different communities from research (Internet Topology Measurement, Economics, Theoretical Computer Science, Network Science) and related industry (ISPs, Content Providers, CDNs etc.) to help narrow the gap between research and operational practice.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022\/\/arc.gatech.edu\/sites\/arc.gatech.edu\/files\/ARC%20Internet%20Topology%20Economics7_0.pdf\u0022\u003EWorkshop Poster [PDF]\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~dovrolis\/wite12\/\u0022\u003EComplete Details\u003C\/a\u003E\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":"","uid":"27263","created_gmt":"2012-10-01 13:50:59","changed_gmt":"2016-10-08 02:00:10","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-11-12T07:30:00-05:00","event_time_end":"2012-11-14T15:30:00-05:00","event_time_end_last":"2012-11-14T15:30:00-05:00","gmt_time_start":"2012-11-12 12:30:00","gmt_time_end":"2012-11-14 20:30:00","gmt_time_end_last":"2012-11-14 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\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"151061":{"#nid":"151061","#data":{"type":"event","title":"ARC\/ACO Colloquium: Alexander Razborov, University of Chicago","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EFlag Algebras\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EA substantial part of extremal combinatorics studies relations existing between densities with which given combinatorial structures (fixed size ``templates\u0027\u0027) may appear in unknown (and presumably very large) structures of the same type.\u003C\/p\u003E\u003Cp\u003EUsing basic tools and concepts from algebra, analysis and measure theory, we develop a general framework that allows to treat all problems of this sort in an uniform way and reveal mathematical structure that is common for many known arguments in the area. The backbone of this structure is made by certain commutative algebras depending on the problem in question.\u003C\/p\u003E\u003Cp\u003EOnce understood, it gives rise to the possibility of computer-aided theorem proving in this area based upon semi-definite programming.\u003C\/p\u003E\u003Cp\u003EIn this talk I will give a general impression of how things work in this framework, and we will pay a special attention to concrete applications\u0026nbsp; of our methods.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Flag Algebras"}],"uid":"27263","created_gmt":"2012-09-04 07:56:38","changed_gmt":"2016-10-08 01:59:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-11-05T12:00:00-05:00","event_time_end":"2012-11-05T12:00:00-05:00","event_time_end_last":"2012-11-05T12:00:00-05:00","gmt_time_start":"2012-11-05 17:00:00","gmt_time_end":"2012-11-05 17:00:00","gmt_time_end_last":"2012-11-05 17: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":[],"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":""}},"150931":{"#nid":"150931","#data":{"type":"event","title":"ARC Colloquium: Sham Kakade, Microsoft Research, New England","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:Tensor Decompositions for Learning Latent Variable Models\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003EIn many applications, we face the challenge of modeling the interactions between multiple observations. A popular and successful approach in machine learning and AI is to hypothesize the existence of certain latent (or hidden) causes which help to explain the correlations in the observed data.\u0026nbsp; The (unsupervised) learning problem is to accurately estimate a model with only samples of the observed data.\u0026nbsp; For example, in document modeling, we may wish to characterize the correlational structure of the \u0022bag of words\u0022 in documents. Here, a standard model is to posit that documents are about a few topics (the hidden variables) and that each active topic determines the occurrence of words in the document. The learning problem is, using only the observed words in the documents (and not the hidden topics), to estimate the topic probability vectors (i.e discover the strength by which words tend to appear under different topcis). In practice, a broad class of latent variable models is most often fit with either local search heuristics (such as the EM algorithm) or sampling based approaches.\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E\u003Cbr \/\u003EThis talk will discuss how generalizations of standard linear algebra tools (e.g. spectral methods) to tensors provide provable and efficient estimation methods for various latent variable models (under appropriate assumptions), including mixtures of Gaussians models, hidden Markov models, topic models, latent Dirichlet allocation, latent parse tree models (PCFGs and dependency parsers), and models for communities in social networks.\u0026nbsp; The talk will also briefly discuss how matrix and tensor decomposition methods can be used for the structure learning problem of determining both the existence of certain hidden causes and the underlying graphical structure between these hidden causes and the observed variables.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Tensor Decompositions for Learning Latent Variable Models"}],"uid":"27263","created_gmt":"2012-08-31 11:38:29","changed_gmt":"2016-10-08 01:59:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-10-29T14:00:00-04:00","event_time_end":"2012-10-29T14:00:00-04:00","event_time_end_last":"2012-10-29T14:00:00-04:00","gmt_time_start":"2012-10-29 18:00:00","gmt_time_end":"2012-10-29 18:00:00","gmt_time_end_last":"2012-10-29 18: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":[],"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":""}},"151081":{"#nid":"151081","#data":{"type":"event","title":"ARC Colloquium: Friedrich Eisenbrand, EPFL, Lausanne","body":[{"value":"\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: Diameter of Polyhedra: Abstractions, new upper bounds and open problems\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EOne of the most prominent mysteries in convex geometry is the question whether the diameter of a polyhedron is bounded by a polynomial in the number of facets. The gap between the best known lower bound (linear) and the best known upper bound (n^{log d} by Kalai and Kleitman) is impressive.\u003C\/p\u003E\u003Cp\u003EAfter Francisco Santos refuted the classical Hirsch conjecture in 2010, the polynomial Hirsch conjecture, stating that the answer to the question above is \u0022Yes\u0022, has received considerable attention. In this talk I present the best known bounds mentioned above in a very simple abstract setting that does not involve any geometry. The polynomial Hirsch conjecture is also open in this abstract setting. I furthermore show polynomial upper bounds on the diameter of polyhedra that are defined by matrices with small sub-determinants and close with open problems.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Diameter of Polyhedra: Abstractions, new upper bounds and open problems"}],"uid":"27263","created_gmt":"2012-09-04 08:25:26","changed_gmt":"2016-10-08 01:59:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-10-22T14:00:00-04:00","event_time_end":"2012-10-22T14:00:00-04:00","event_time_end_last":"2012-10-22T14:00:00-04:00","gmt_time_start":"2012-10-22 18:00:00","gmt_time_end":"2012-10-22 18:00:00","gmt_time_end_last":"2012-10-22 18: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":[],"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":""}},"156671":{"#nid":"156671","#data":{"type":"event","title":"Theory Seminar: Stephen Young, University of Louisville, Kentucky","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Braess\u0027s Paradox in Expanders\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EExpander graphs are known to facilitate effective routing and most real-world networks have expansion properties. At the other extreme, it has been shown that in some special graphs, removing certain edges can lead to more efficient routing. This phenomenon is known as Braess\u00b9s paradox and is usually regarded as a rare event. In contrast to what one might expect, we show that Braess\u00b9s paradox is ubiquitous in expander graphs. Specifically, we prove that Braess\u00b9s paradox occurs in a large class of expander graphs with continuous convex latency functions. Our results extend previous work which held only when the graph was both denser and random and for random linear latency functions. We identify deterministic sufficient conditions for a graph with as few as a linear number of edges, such that Braess\u00b9s Paradox almost always occurs, with respect to a general family of random latency functions.\u0026nbsp; (Joint work with Fan Chung and Wenbo Zhao.)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-09-25 09:25:32","changed_gmt":"2016-10-08 02:00:10","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-10-08T14:05:00-04:00","event_time_end":"2012-10-08T14:05:00-04:00","event_time_end_last":"2012-10-08T14:05:00-04:00","gmt_time_start":"2012-10-08 18:05:00","gmt_time_end":"2012-10-08 18:05:00","gmt_time_end_last":"2012-10-08 18:05: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":[],"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":""}},"150911":{"#nid":"150911","#data":{"type":"event","title":"ARC Colloquium: Ravi Kannan, Microsoft Research, India","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: k-MEANS REVISITED\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EIn many applications, fairly fast clustering algorithms seem to yield the desired solution. Theoretically, two types of assumptions lead to provably fast algorithms for clustering:\u003C\/p\u003E\u003Cp\u003E(i) stochastic (mixture) models of data and (ii) uniqueness of optimal solution even under perturbations of data. We show that under an assumption weaker than either of these, Lloyd\u0027s (k-means) algorithm converges to the correct solution. We apply the result to the planted clique problem.\u003C\/p\u003E\u003Cp\u003EJoint work with Amit Kumar.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-08-31 11:36:10","changed_gmt":"2016-10-08 01:59:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-09-17T14:00:00-04:00","event_time_end":"2012-09-17T14:00:00-04:00","event_time_end_last":"2012-09-17T14:00:00-04:00","gmt_time_start":"2012-09-17 18:00:00","gmt_time_end":"2012-09-17 18:00:00","gmt_time_end_last":"2012-09-17 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"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":""}},"151091":{"#nid":"151091","#data":{"type":"event","title":"ARC Colloquium: Shachar Lovett, Institute of Advanced Study, Princeton, NJ","body":[{"value":"\u003Cp\u003E\u003Cbr \/\u003E\u003Cstrong\u003ETitle: Constructive Discrepancy Minimization by Walking on The Edges\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMinimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of\u0026nbsp;$n$ sets in a universe of size $n$, there always exists a coloring which achieves discrepancy $6\\sqrt{n}$. The original proof of Spencer was existential\u0026nbsp;in nature, and did not give an efficient algorithm to find such a coloring.\u003C\/p\u003E\u003Cp\u003ERecently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an\u0026nbsp;SDP relaxation of the discrepancy problem and a clever rounding procedure. In this work we give a new randomized algorithm to find a \u003Cbr \/\u003Ecoloring as in Spencer\u0027s result based on a restricted random walk we call Edge-Walk. Our algorithm and its analysis use only basic linear algebra and is \u0022truly\u0022 constructive in that it does not appeal to the existential arguments,giving a new proof of Spencer\u0027s theorem and the partial coloring lemma.\u003C\/p\u003E\u003Cp\u003EJoint work with Raghu Meka\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-09-04 08:36:09","changed_gmt":"2016-10-08 01:59:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-09-10T14:00:00-04:00","event_time_end":"2012-09-10T14:00:00-04:00","event_time_end_last":"2012-09-10T14:00:00-04:00","gmt_time_start":"2012-09-10 18:00:00","gmt_time_end":"2012-09-10 18:00:00","gmt_time_end_last":"2012-09-10 18: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":[],"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":""}},"148351":{"#nid":"148351","#data":{"type":"event","title":"Joint ARC and School of Math Colloquium by Noga Alon, Tel Aviv University, Israel","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: Coloring Random Cayley Graphs\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe study of random Cayley graphs of finite groups is related to the investigation of Expanders and to problems in Combinatorial Number Theory and in Information Theory. I will discuss this topic, describing the motivation and focusing on the question of estimating the chromatic number of a random Cayley graph of a given\u0026nbsp; group with a prescribed number of generators. The investigation of this problem combines combinatorial, algebraic and probabilistic tools. Several intriguing questions that remain open will be mentioned as well.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-08-21 14:50:46","changed_gmt":"2016-10-08 01:59:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-09-06T12:00:00-04:00","event_time_end":"2012-09-06T12:00:00-04:00","event_time_end_last":"2012-09-06T12:00:00-04:00","gmt_time_start":"2012-09-06 16:00:00","gmt_time_end":"2012-09-06 16:00:00","gmt_time_end_last":"2012-09-06 16: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":[],"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":""}},"129481":{"#nid":"129481","#data":{"type":"event","title":"ARC5 -  Distinguished Lecture  by Noga Alon, Tel Aviv University, Israel and Persi Diaconis, Stanford University","body":[{"value":"\u003Cp\u003ESpeaker: Noga Alon, Tel Aviv University\u003C\/p\u003E\u003Cp\u003ETitle: On graphs, arithmetic progressions and communication\u003C\/p\u003E\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003ETools from Extremal Graph Theory are helpful in the study of problems in Additive Number Theory, Theoretical Computer Science, and Information Theory. I will illustrate this fact by several closely related examples focusing on a recent one in a joint paper with Moitra and Sudakov.\u003C\/p\u003E\u003Cp\u003ESpeaker: Persi Diaconis\u003C\/p\u003E\u003Cp\u003ETitle: \u0022An Introduction to additive combinatorics via \u0027carries\u0027\u0022\u003C\/p\u003E\u003Cp\u003EAbstract\u003C\/p\u003E\u003Cp\u003EWhen numbers are added in the usual way, \u0022carries\u0022 occur.\u0026nbsp; The chance of a carry is about .45 (base 10).\u0026nbsp; There are other choices of digits that lead to fewer carries (balanced digits).\u0026nbsp; These balanced systems turn out to be best (fewest carries).\u0026nbsp; Showing this requires an excursion into additive combinatorics a la Gowers-Green-Szemeredi-Tao.\u0026nbsp; This is joint work with Shao and Soundarajan.\u003C\/p\u003E\u003Cp\u003ESee All Workshop presentations and videos\u003Ca href=\u0022http:\/\/smartech.gatech.edu\/handle\/1853\/45038\u0022\u003E here\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/hg.gatech.edu\/sites\/default\/files\/arc5-program.pdf\u0022\u003EProgram\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ESchedule\u003C\/strong\u003E\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003E9:00 am - Breakfast (Klaus atrium)\u003C\/li\u003E\u003Cli\u003E9:30 am - Keynote: Noga Alon\u003C\/li\u003E\u003Cli\u003E10:30 am - Break\u003C\/li\u003E\u003Cli\u003E10:45 am - Talks (25 min each) by:\u003Cul\u003E\u003Cli\u003EGreg Blekherman (Math)\u003C\/li\u003E\u003Cli\u003EFrank Dellaert (CoC)\u003C\/li\u003E\u003Cli\u003EJustin Romberg (ECE)\u003C\/li\u003E\u003C\/ul\u003E\u003C\/li\u003E\u003Cli\u003E12:15 pm - Lunch (Klaus atrium, with the student poster session for viewing)\u003C\/li\u003E\u003Cli\u003E1:30 pm - Keynote: Persi Diaconis\u003C\/li\u003E\u003C\/ul\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-05-10 08:59:19","changed_gmt":"2016-10-08 01:58:53","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-08-28T10:00:00-04:00","event_time_end":"2012-08-28T10:00:00-04:00","event_time_end_last":"2012-08-28T10:00:00-04:00","gmt_time_start":"2012-08-28 14:00:00","gmt_time_end":"2012-08-28 14:00:00","gmt_time_end_last":"2012-08-28 14: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":[],"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":""}},"124171":{"#nid":"124171","#data":{"type":"event","title":"Computation and Phase Transitions Workshop","body":[{"value":"\u003Cp\u003EWorkshop Theme:\u003C\/p\u003E\u003Cp\u003EThe workshop on Computation and Phase Transitions brings together researchers from Statistical Physics, Probability, Discrete Mathematics, and Theoretical Computer Science. The convergence of ideas from these fields has led to breakthroughs in our understanding of the limits of computation for approximate counting and random sampling problems. For example, recent algorithmic work of Dror Weitz and inapproximability work of Allan Sly shows that the computational complexity of approximately counting weighted independent sets in general graphs undergoes a phase transtion on trees.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~vigoda\/new-workshop\/\u0022\u003Ehttp:\/\/www.cc.gatech.edu\/~vigoda\/new-workshop\/\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-04-16 09:55:38","changed_gmt":"2016-10-08 01:58:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-06-04T14:00:00-04:00","event_time_end":"2012-06-07T22:00:00-04:00","event_time_end_last":"2012-06-07T22:00:00-04:00","gmt_time_start":"2012-06-04 18:00:00","gmt_time_end":"2012-06-08 02:00:00","gmt_time_end_last":"2012-06-08 02: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":[],"invited_audience":[],"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":""}},"129151":{"#nid":"129151","#data":{"type":"event","title":"ARC Colloquium: Devavrat Shah, MIT","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such net-works have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. As the main result, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a long-standing conjecture about optimal queue-size scaling for input-queued switches.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;This is based on joint work with Neil Walton (Univ of Amsterdam) and Yuan Zhong (MIT).\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;Bio\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;Devavrat Shah is currently a Jamieson associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and Operations Research Center (ORC). His research focus is on theory of large complex networks which includes network algorithms and statistical inference.\u0026nbsp; He has received 2008 ACM Sigmetrics Rising Star Award and 2010 Erlang Prize from the Applied Probability Society of INFORMS. He currently serves as an associate editor of\u0026nbsp; Operations Research.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Optimal queue-size scaling in switched networks"}],"uid":"27263","created_gmt":"2012-05-08 17:20:56","changed_gmt":"2016-10-08 01:58:53","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-05-31T16:00:00-04:00","event_time_end":"2012-05-31T16:00:00-04:00","event_time_end_last":"2012-05-31T16:00:00-04:00","gmt_time_start":"2012-05-31 20:00:00","gmt_time_end":"2012-05-31 20:00:00","gmt_time_end_last":"2012-05-31 20: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":[],"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":""}},"124211":{"#nid":"124211","#data":{"type":"event","title":"ARC-RIM Industry Day","body":[{"value":"\u003Cp\u003EObjective\u003C\/p\u003E\u003Cp\u003EThe objective of this workshop is to bring together leading researchers\/developers from industry with leading researchers from academia to discuss challenges, opportunities and new trends in logistics, material handling, optimization, and related algorithms.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/robotics.gatech.edu\/content\/arc-rim-industry-day\u0022\u003Ehttp:\/\/robotics.gatech.edu\/content\/arc-rim-industry-day\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2012-04-16 10:44:03","changed_gmt":"2016-10-08 01:58:45","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-05-04T13:45:00-04:00","event_time_end":"2012-05-04T22:00:00-04:00","event_time_end_last":"2012-05-04T22:00:00-04:00","gmt_time_start":"2012-05-04 17:45:00","gmt_time_end":"2012-05-05 02:00:00","gmt_time_end_last":"2012-05-05 02: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":"26411","name":"Training\/Workshop"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:nwhite@cc.gatech.edu\u0022\u003Enwhite@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"122291":{"#nid":"122291","#data":{"type":"event","title":"Jason Hartline, Northwestern University","body":[{"value":"\u003Cp\u003ETitle: The Simple Economics of Approximately Optimal Auctions\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E Systems wherein strategic agents compete for limited resources are ubiquitous: the economy, computer networks, social networks, congestion networks, etc.\u0026nbsp; Auction theory governs the design and analysis of these systems.\u0026nbsp; I will describe a method for using approximation in auction theory to identify simple, practical, and robust auction mechanisms that perform nearly as well as the complex optimal ones.\u0026nbsp; A main goal of this approach is to understand the extent to which important intuition from optimal auctions for ideal models extends to approximately optimal auctions for more realistic models.\u003C\/p\u003E\u003Cp\u003EAuction theory is well understood only in ideal models where agents have single-dimensional, linear preferences.\u0026nbsp; I.e., each agent has a value for receiving a service and her utility is the difference between her value and her payment.\u0026nbsp; For these models optimal auctions can be interpreted as \u0022marginal revenue\u0022 maximizers (Myerson, 1981; Bulow and Roberts 1989).\u0026nbsp; In more realistic models, i.e., where bidders have multi-dimensional preferences for different outcomes or non-linear utility, similar intuitive characterizations are unknown.\u0026nbsp; Understanding good auctions for these environments is considered to be the main challenge in auction theory.\u0026nbsp; In these more realistic environments maximizing marginal revenue may not be optimal, and furthermore, there is sometimes no direct way to implementing the marginal revenue maximization mechanism. I will present two results:\u0026nbsp; I will give procedures for implementing marginal revenue maximization in general, and I will show that marginal revenue maximization is approximately optimal.\u0026nbsp; The approximation factor smoothly degrades in a term that quantifies how far the environment is from an ideal one (i.e., where marginal revenue maximization is optimal).\u003C\/p\u003E\u003Cp\u003EJoint work with Saeed Alaei, Hu Fu, Nima Haghpanah, and Azarakhsh Malekian.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"The Simple Economics of Approximately Optimal Auctions"}],"uid":"27263","created_gmt":"2012-04-05 11:45:24","changed_gmt":"2016-10-08 01:58:41","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-04-23T18:00:00-04:00","event_time_end":"2012-04-23T18:00:00-04:00","event_time_end_last":"2012-04-23T18:00:00-04:00","gmt_time_start":"2012-04-23 22:00:00","gmt_time_end":"2012-04-23 22:00:00","gmt_time_end_last":"2012-04-23 22: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":[],"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":""}},"108011":{"#nid":"108011","#data":{"type":"event","title":"ARC Colloquium: Sebastian Lahaie, Yahoo! Research","body":[{"value":"\u003Cp\u003ETitle: A Kernel-Based Combinatorial Auction\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EIn this \u0026nbsp;talk \u0026nbsp;I present an iterative combinatorial auction that \u0026nbsp;offers modularity in the \u0026nbsp;choice of \u0026nbsp;price \u0026nbsp;structure, \u0026nbsp;drawing on \u0026nbsp;ideas \u0026nbsp;from kernel \u0026nbsp;methods and \u0026nbsp;the primal-dual paradigm of \u0026nbsp;auction design. \u0026nbsp;The \u0026nbsp;auction is able \u0026nbsp;to \u0026nbsp;automatically detect, \u0026nbsp;as\u0026nbsp; \u0026nbsp;the\u0026nbsp; \u0026nbsp;rounds \u0026nbsp;progress,\u0026nbsp; \u0026nbsp;whether \u0026nbsp;price\u0026nbsp;\u0026nbsp; \u0026nbsp;expressiveness\u0026nbsp; \u0026nbsp;must\u0026nbsp;\u0026nbsp; \u0026nbsp;be increased to \u0026nbsp;clear \u0026nbsp;the \u0026nbsp;market, and \u0026nbsp;converges to \u0026nbsp;a \u0026nbsp;sparse \u0026nbsp;representation of nonlinear clearing prices. \u0026nbsp;I show \u0026nbsp;that \u0026nbsp;by \u0026nbsp;introducing regularization the auction is able to compute approximate truth-inducing payments in just a single \u0026nbsp;run, in contrast to VCG payments which require as many \u0026nbsp;runs as there \u0026nbsp;are bidders. An empirical evaluation demonstrates the performance gains\u0026nbsp; that \u0026nbsp;can be obtained in \u0026nbsp;allocative efficiency, \u0026nbsp;revenue, \u0026nbsp;and \u0026nbsp;rounds to \u0026nbsp;convergence through various configurations of \u0026nbsp;the \u0026nbsp;auction design against \u0026nbsp;established linear-\u0026nbsp; \u0026nbsp;and \u0026nbsp;bundle- price \u0026nbsp;auctions.\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/hg.gatech.edu\/sites\/default\/files\/sebastien_lahaie_4_16_12_ga_2.pdf\u0022\u003EPoster [PDF]\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Kernel-Based Combinatorial Auction"}],"uid":"27263","created_gmt":"2012-02-09 10:50:06","changed_gmt":"2016-10-08 01:58:00","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-04-16T14:00:00-04:00","event_time_end":"2012-04-16T14:00:00-04:00","event_time_end_last":"2012-04-16T14:00:00-04:00","gmt_time_start":"2012-04-16 18:00:00","gmt_time_end":"2012-04-16 18:00:00","gmt_time_end_last":"2012-04-16 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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\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":""}},"120221":{"#nid":"120221","#data":{"type":"event","title":"Prosenjit Bose, Carleton University, Canada","body":[{"value":"\u003Cp\u003ETitle: Competitive Routing on a Variant of the Delaunay Triangulation\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5\/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Competitive Routing on a Variant of the Delaunay Triangulation"}],"uid":"27263","created_gmt":"2012-03-28 16:24:09","changed_gmt":"2016-10-08 01:58:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-04-05T18:30:00-04:00","event_time_end":"2012-04-05T18:30:00-04:00","event_time_end_last":"2012-04-05T18:30:00-04:00","gmt_time_start":"2012-04-05 22:30:00","gmt_time_end":"2012-04-05 22:30:00","gmt_time_end_last":"2012-04-05 22: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":[],"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":""}},"81101":{"#nid":"81101","#data":{"type":"event","title":"ARC Colloquium: Constantinos Daskalakis (MIT)","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ETitle: Multidimensional Revenue Optimization\u003C\/p\u003E\u003Cp\u003EIn his seminal paper, Myerson [1981] provided a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;(joint work with Yang Cai and Matt Weinberg)\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Multidimensional Revenue Optimization"}],"uid":"27263","created_gmt":"2012-01-23 08:55:59","changed_gmt":"2016-10-08 01:49:23","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-03-26T14:00:00-04:00","event_time_end":"2012-03-26T14:00:00-04:00","event_time_end_last":"2012-03-26T14:00:00-04:00","gmt_time_start":"2012-03-26 18:00:00","gmt_time_end":"2012-03-26 18:00:00","gmt_time_end_last":"2012-03-26 18: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":[],"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":""}},"71907":{"#nid":"71907","#data":{"type":"event","title":"ARC Submodularity Workshop","body":[{"value":"\u003Cp\u003EWorkshop Theme:\u003Cbr \/\u003ESubmodular functions are discrete analogues of convex functions, arising in various fields of computer science and operations research. Since the seminal work of Jack Edmonds (1970), submodularity has long been recognized as a common structure of many efficiently solvable combinatorial optimization problems. Recent algorithmic developments in the past decade include combinatorial strongly polynomial algorithm for minimization, constant factor approximation algorithms for maximization, and efficient methods for learning submodular functions. In addition, submodular functions find novel applications in combinatorial auctions, machine learning, and social networks. This workshop aims at providing a forum for researchers from a variety of backgrounds for exchanging results, ideas, and problems on submodular optimization and its applications. The first day will be devoted to tutorial-style lectures!\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Ca href=\u0022http:\/\/hg.gatech.edu\/sites\/default\/files\/submod-workshopposter_4.pdf\u0022\u003EPoster [PDF]\u003C\/a\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www2.isye.gatech.edu\/submodularity-workshop\u0022 target=\u0022_blank\u0022\u003EComplete Details\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003EVideos of all the tutorial sessions:\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003EAndreas Krause, \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43255\/02krause_streaming.html?sequence=2\u0022 target=\u0022_blank\u0022\u003E Submodular Function Optimization in Sensor and Social Networks\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003EAndreas Krause, \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43256\/03krause_streaming.html?sequence=2\u0022 target=\u0022_blank\u0022\u003E Submodular Function Optimization in Sensor and Social Networks II\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003EKazuo Murota, \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43257\/04murota_streaming.html?sequence=2\u0022 target=\u0022_blank\u0022\u003E Introduction to Discrete Convex Analysis\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003EKazuo Murota, \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43258\/05murota_streaming.html?sequence=2\u0022 target=\u0022_blank\u0022\u003E Minimization and Maximization Algorithms in Discrete Convex Analysis\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003EJan Vondrak, \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43254\/01vondrak_streaming.html?sequence=2\u0022 target=\u0022_blank\u0022\u003E Optimization of Submodular Functions: Relaxations and Algorithms\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003EJan Vondrak, \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/bitstream\/handle\/1853\/43259\/06vondrak_streaming.html?sequence=2\u0022 target=\u0022_blank\u0022\u003E Optimization of Submodular Functions: Hardness and Optimality\u003C\/a\u003E\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003ESee all \u003Ca href=\u0022http:\/\/smartech.gatech.edu\/handle\/1853\/45037\u0022 target=\u0022_blank\u0022\u003Eworkshop presentations and videos\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2011-10-25 16:32:06","changed_gmt":"2016-10-08 01:56:28","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-03-19T10:00:00-04:00","event_time_end":"2012-03-22T17:00:00-04:00","event_time_end_last":"2012-03-22T17:00:00-04:00","gmt_time_start":"2012-03-19 14:00:00","gmt_time_end":"2012-03-22 21:00:00","gmt_time_end_last":"2012-03-22 21: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":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"77691":{"#nid":"77691","#data":{"type":"event","title":"ARC Colloquium: Eli Ben-Sasson, Technion - Israel Institute of Technology","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFor a {0,1}-valued matrix M let CC(M) denote the deterministic communication complexity of the boolean function associated with M. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC(M) \u0026lt;= log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank of M over the field of real numbers.\u003C\/p\u003E\u003Cp\u003EWe show that CC(M) \u0026lt;= c rank(M)\/ log rank(M) for some absolute constant c, assuming a well-known conjecture from additive combinatorics, known as the Polynomial Freiman-Ruzsa (PFR) conjecture.\u003C\/p\u003E\u003Cp\u003EOur proof is based on the study of the \u0022approximate duality conjecture\u0022 which was recently suggested by Ben-Sasson and Zewi [STOC 2011], and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, and this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995]. \u003C\/p\u003E\u003Cp\u003EJoint work with Shachar Lovett and Noga Zewi\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"An Additive Combinatorics Approach to the Study of the Log-rank Conjecture in Communication Complexity"}],"uid":"27263","created_gmt":"2012-01-11 16:46:13","changed_gmt":"2016-10-08 01:57:02","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-03-12T14:00:00-04:00","event_time_end":"2012-03-12T14:00:00-04:00","event_time_end_last":"2012-03-12T14:00:00-04:00","gmt_time_start":"2012-03-12 18:00:00","gmt_time_end":"2012-03-12 18:00:00","gmt_time_end_last":"2012-03-12 18: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":[],"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":""}}}