{"254491":{"#nid":"254491","#data":{"type":"event","title":"ARC Colloquium: Adam Marcus, Crisply.com and Yale University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ESpeaker:\u003C\/strong\u003E Adam Marcus\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Interlacing Families and Bipartite Ramanujan Graphs\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EWe will outline the proof that shows the existence of bipartite Ramanujan Graphs of any degree as well as some of mixed degrees. Our approach uses the idea of Bilu and Linial to show that there exists a 2-lift of a given Ramanujan graph which maintains the Ramanujan property.\u0026nbsp; This will include introducing a new technique for establishing the existence of certain combinatorial objects that we call the \u0022Method of Interlacing Polynomials.\u0022\u003C\/p\u003E\u003Cp\u003EThis talk is intended to be accessible by a general computer science audience, and represents joint work with Dan Spielman and Nikhil Srivastava.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-11-14 10:30:10","changed_gmt":"2017-04-13 21:23:51","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-12-09T14:00:00-05:00","event_time_end":"2013-12-09T14:00:00-05:00","event_time_end_last":"2013-12-09T14:00:00-05:00","gmt_time_start":"2013-12-09 19:00:00","gmt_time_end":"2013-12-09 19:00:00","gmt_time_end_last":"2013-12-09 19:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"254811":{"#nid":"254811","#data":{"type":"event","title":"ARC Colloquium: Sivan Sabato, Microsoft Research New England","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ESpeaker:\u003C\/strong\u003E Sivan Sabato\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E \u003Cstrong\u003EAuditing: Active Learning with Outcome-Dependent Query Costs\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EWe propose a learning setting in which unlabeled data is free, and the cost of a label depends on its value, which is not known in advance. Specifically, we study binary classification in an extreme case, where the algorithm only pays for negative labels. Our motivation is applications such as fraud detection, in which investigating an honest transaction should be avoided if possible. We term the setting \u0022auditing\u0022, and consider the \u0022auditing complexity\u0022 of an algorithm. We design auditing algorithms for simple hypothesis classes, \u003Cbr \/\u003E and show that with these algorithms, the auditing complexity can be significantly lower than the active label complexity. We also consider a general competitive approach for auditing,\u003C\/p\u003E\u003Cp\u003Eand demonstrate its potential for linear classification.\u003C\/p\u003E\u003Cp\u003EJoint work with Anand Sarwate and Nati Srebro from TTI-Chicago\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-11-14 17:00:32","changed_gmt":"2017-04-13 21:23:51","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-11-25T12:00:00-05:00","event_time_end":"2013-11-25T12:00:00-05:00","event_time_end_last":"2013-11-25T12:00:00-05:00","gmt_time_start":"2013-11-25 17:00:00","gmt_time_end":"2013-11-25 17:00:00","gmt_time_end_last":"2013-11-25 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":"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":""}},"250021":{"#nid":"250021","#data":{"type":"event","title":"ARC Colloquium: Francois Baccelli, The University of Texas at Austin","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Geometric Routing in Stochastic Networks, Point-Shift and Palm Probabilities of a Point Process\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EConsider a point process in the Euclidean space and a rule defining the edges that exist between its points. This defines a random graph on the point process. A routing algorithm constructs, for all pairs of points, a route between these points, namely a path of this graph connecting them, when possible. Such an algorithm can be global, like in shortest path routing, or local, like in geographic or geometric routing.\u003C\/p\u003E\u003Cp\u003EThis talk will discuss properties of routes which are locally defined on a stationary point process, using the notion of point-shift.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;A point-shift maps, in a translation invariant way, each point of a stationary point process Z to some point of Z. The existence of stationary regimes of a routing algorithm is then equivalent to that of probability measures, defined on the space of counting measures with an atom at the origin, which are left invariant by the point-shift f describing the local algorithm. The point-shift probabilities of Z are defined from the action of the semigroup of point-shift translations on the space of Palm probabilities, and more precisely from the compactification of the orbits of this semigroup action. If the point-shift probability is uniquely defined, and if f is continuous with respect to the vague topology, then the point-shift probability of Z provides a solution to the stationary regime question.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;Point-shift probabilities are shown to be a strict generalization of Palm probabilities: when the considered point-shift f is bijective, the point-shift-probability of Z boils down to the Palm probability of Z. When it is not bijective, there exist cases where the point-shift-probability of Z is the law of Z under the Palm probability of some stationary thinning Y of Z. But there also exist cases where the point-shift-probability of Z is singular w.r.t. the Palm probability of Z and where, in addition, it cannot be the law of Z under the Palm probability of any stationary point process Y jointly stationary with Z. The talk will give a criterion for the existence of point-shift probabilities of a stationary point process and will discuss uniqueness. The results will be illustrated through several examples.\u003C\/p\u003E\u003Cp\u003EJoint work with Mir-Omid Haji-Mirsadeghi, Sharif University, Department of Mathematics.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-10-31 10:04:32","changed_gmt":"2016-10-08 02:05:30","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-11-08T15:00:00-05:00","event_time_end":"2013-11-08T15:00:00-05:00","event_time_end_last":"2013-11-08T15:00:00-05:00","gmt_time_start":"2013-11-08 20:00:00","gmt_time_end":"2013-11-08 20:00:00","gmt_time_end_last":"2013-11-08 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\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":""}},"238831":{"#nid":"238831","#data":{"type":"event","title":"ARC Colloquium: Kuang Xu, Massachusetts Institute of Technology","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Queueing System Topologies with Limited Flexibility\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E: We study a multi-server model with n flexible servers and rn queues, connected through a fixed bipartite graph, where the level of flexibility is captured by the average degree, d(n), of the queues. Applications in content replication in data centers, skill-based routing in call centers, and flexible\u0026nbsp; supply chains are among our main motivations.\u003C\/p\u003E\u003Cp\u003E\u003Cbr \/\u003E We focus on the scaling regime where the system size n tends to in\ufb01nity, while the overall traf\ufb01c intensity stays \ufb01xed. We show that a large capacity region (robustness) and diminishing queueing delay (performance) are jointly achievable even under very limited flexibility (d(n) \u0026lt;\u0026lt; n). In particular, when d(n) \u0026gt;\u0026gt; ln(n), a family of random-graph-based interconnection topologies is (with high probability) capable of stabilizing all admissible arrival rate vectors (under a bounded support assumption), while simultaneously ensuring a diminishing queueing delay, of order ln(n)\/d(n), as n tends to infinity. Our analysis is centered around a new class of virtual-queue-based scheduling policies that rely on dynamically constructed partial matchings on the connectivity graph. We also compare different architectures in terms of to what extend the joint objective of capacity and delay is possible.\u003C\/p\u003E\u003Cp\u003EBased on joint work with John N. Tsitsiklis.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-09-19 08:27:55","changed_gmt":"2016-10-08 02:04:51","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-10-28T14:30:00-04:00","event_time_end":"2013-10-28T14:30:00-04:00","event_time_end_last":"2013-10-28T14:30:00-04:00","gmt_time_start":"2013-10-28 18:30:00","gmt_time_end":"2013-10-28 18:30:00","gmt_time_end_last":"2013-10-28 18:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\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":""}},"205831":{"#nid":"205831","#data":{"type":"event","title":"ARC Colloquium: Vitaly Feldman, IBM Almaden Research Center, San Jose, CA.","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Statistical Algorithms and a Lower Bound for Detecting Planted Cliques\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalizes the statistical query model in learning theory.\u003C\/p\u003E\u003Cp\u003EOur main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n^(1\/2-\\delta)) for any constant \\delta \u0026gt; 0. Variants of these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.\u003C\/p\u003E\u003Cp\u003EJoint work with Elena Grigorescu, Lev Reyzin, Santosh Vempala and Ying Xiao\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":"2013-04-11 10:53:19","changed_gmt":"2016-10-08 02:03:16","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-05-01T14:00:00-04:00","event_time_end":"2013-05-01T14:00:00-04:00","event_time_end_last":"2013-05-01T14:00:00-04:00","gmt_time_start":"2013-05-01 18:00:00","gmt_time_end":"2013-05-01 18:00:00","gmt_time_end_last":"2013-05-01 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":[],"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":""}},"200111":{"#nid":"200111","#data":{"type":"event","title":"ARC Colloquium: Maxim Raginsky, University of Illinois at Urbana-Champaign","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;Logarithmic Sobolev inequalities and strong data processing theorems for discrete channels\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe problem of quantifying the amount of information loss due to a random transformation (or a noisy channel) arises in a variety of contexts, such as machine learning, stochastic simulation, error-correcting codes, or computation in circuits with noisy gates, to name just a few. This talk will focus on discrete channels, where both the input and output sets are finite.\u0026nbsp; The noisiness of a discrete channel can be measured by comparing suitable functionals of the input and output distributions. For instance, if we fix a reference input distribution, then the worst-case ratio of output relative entropy (Kullback-Leibler divergence) to input relative entropy for any other input distribution is bounded by one, by the data processing theorem. However, for a fixed reference input distribution, this quantity may be strictly smaller than one, giving so-called strong data processing inequalities (SDPIs). I will show that the problem of determining both the best constant in an SDPI and any input distributions that achieve it can be addressed using logarithmic Sobolev inequalities, which relate input relative entropy to certain measures of input-output correlation. I will also show that SDPIs for Kullback-Leibler divergence arises as a limiting case of a family of SDPIs for Renyi divergence, and discuss the relationship to hypercontraction of Markov operators.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E\u0026nbsp;Bio:\u003C\/strong\u003E Maxim Raginsky received the B.S. and M.S. degrees in 2000 and the Ph.D. degree in 2002 from Northwestern University, Evanston, IL, all in electrical engineering. He has held research positions with Northwestern, the University of Illinois at Urbana-Champaign (where he was a Beckman Foundation Fellow from 2004 to 2007), and Duke University. In 2012, he has returned to UIUC, where he is currently an Assistant Professor with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory. In 2013, Prof. Raginsky has received a Faculty Early Career Development (CAREER) Award from the National Science Foundation. His research interests lie at the intersection of information theory, machine learning, and control.\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":"2013-03-18 11:54:15","changed_gmt":"2016-10-08 02:02:55","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-29T16:00:00-04:00","event_time_end":"2013-04-29T16:00:00-04:00","event_time_end_last":"2013-04-29T16:00:00-04:00","gmt_time_start":"2013-04-29 20:00:00","gmt_time_end":"2013-04-29 20:00:00","gmt_time_end_last":"2013-04-29 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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":""}},"205791":{"#nid":"205791","#data":{"type":"event","title":"ARC Colloquium: David Woodruff, IBM Almaden Research Center, San Jose, CA.","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Low Rank Approximation and Regression in Input Sparsity Time \u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EWe improve the running times of algorithms for least squares regression and low-rank approximation to account for the sparsity of the input matrix. \u0026nbsp;Namely, if nnz (A) denotes the number of non-zero entries of an input matrix A: \u003C\/p\u003E\u003Cul\u003E\u003Cli\u003Ewe show how to solve approximate least squares regression given an n x d matrix A in nnz(A) + poly(d log n) time \u003C\/li\u003E\u003Cli\u003Ewe show how to find an approximate best rank-k approximation of an n x n matrix in nnz(A) + n*poly(k log n) time \u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003EAll approximations are relative error. Previous algorithms based on fast Johnson-Lindenstrauss transforms took at least ndlog d or nnz(A)*k time. We have implemented our algorithms, and preliminary results suggest the algorithms are competitive in practice. \u003C\/p\u003E\u003Cp\u003EJoint work with Ken Clarkson.\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":"2013-04-11 10:39:17","changed_gmt":"2016-10-08 02:03:16","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-26T11:00:00-04:00","event_time_end":"2013-04-26T11:00:00-04:00","event_time_end_last":"2013-04-26T11:00:00-04:00","gmt_time_start":"2013-04-26 15:00:00","gmt_time_end":"2013-04-26 15:00:00","gmt_time_end_last":"2013-04-26 15:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"50877","name":"School of Computational Science and Engineering"},{"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":""}},"191581":{"#nid":"191581","#data":{"type":"event","title":"ARC-RIM Industry Day","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003E\u003Cstrong\u003EOrganizers: \u003C\/strong\u003E\u003Cbr \/\u003EHenrik Christensen (Director of Robotics \u0026amp; Intelligent Machines (RIM, GaTech)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EPrasad Tetali (Director of Algorithms \u0026amp; Randomness Center (ARC), GaTech) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EObjective: \u003C\/strong\u003E\u003Cbr \/\u003EThe objective of this workshop is to bring together leaders and researchers from industry and academia to discuss:\u003C\/p\u003E\u003Cp\u003E(i) challenges, trends, and opportunities in various topics including logistics, supply chain management, display advertisement, and energy efficiency:\u003C\/p\u003E\u003Cp\u003E(ii) how to address them by leveraging state-of-the-art quantitative methods such as optimization, machine learning, algorithms, and stochastics.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAgenda: \u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E08:45-09:15\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Registration\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E09:15-10:15\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Logistics\u003C\/strong\u003E\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003EKevin Gue, Auburn University: \u0022Plug-and-Work Material Handling\u0022\u003C\/li\u003E\u003Cli\u003EHenrik Christensen, Georgia Tech: \u0022Optimization for palletizing and vehicle routing\u0022\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Cstrong\u003E10:15-10:30\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Break\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E10:30-12:30\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Optimization\u003C\/strong\u003E\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003ESebastian Pokutta, Georgia Tech: \u0022Applying Algorithms to Real-World Problems\u0022\u003C\/li\u003E\u003Cli\u003EKen Clarkson, IBM Research: \u0022Low Rank Approximation and Regression in Input Sparsity Time\u0022\u003C\/li\u003E\u003Cli\u003ENitish Korula, Google Research: \u0022Online Matching and Online Display Advertising\u0022\u003C\/li\u003E\u003Cli\u003EKamal Jain, e-Bay: \u0022Business models of buyer-sellers matching\u0022\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Cstrong\u003E12:30-01:15\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Lunch\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E01:15-02:45 Energy and Sustainability\u003C\/strong\u003E\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003EFrederic Villenueve, Siemens Corporation: \u0022The Opportunities of Optimization and Uncertainty Quantification in Energy R\u0026amp;D\u0022\u003C\/li\u003E\u003Cli\u003EDebmalya Panigrahi, Microsoft Research and Duke University: \u0022Energy-efficient Scheduling\u0022\u003C\/li\u003E\u003Cli\u003ENagi Gebraeel, Georgia Tech: \u0022Predictive Analytics for Improving Reliability and Ensuring Sustainability\u0022\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Cstrong\u003E02:45-03:15\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Break\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E03:15-04:00\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Panel of Discussion\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E04:00-05:00\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; Reception\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/robotics.gatech.edu\/content\/arc-rim-industry-day-2013\u0022\u003Ehttp:\/\/robotics.gatech.edu\/content\/arc-rim-industry-day-2013\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/ARC%20Theory%20Day%202013b_0.pdf\u0022\u003EPoster [PDF]\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":"2013-02-12 14:50:52","changed_gmt":"2016-10-08 02:02:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-25T09:00:00-04:00","event_time_end":"2013-04-25T18:00:00-04:00","event_time_end_last":"2013-04-25T18:00:00-04:00","gmt_time_start":"2013-04-25 13:00:00","gmt_time_end":"2013-04-25 22:00:00","gmt_time_end_last":"2013-04-25 22: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":"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":""}},"191591":{"#nid":"191591","#data":{"type":"event","title":"ARC Theory Day","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EObjective:\u003C\/strong\u003E \u0026nbsp;The ARC Theory Day features hour-long lectures focusing on recent innovative results in theoretical computer science, spanning a wide array of topics several of which are inspired by practical problems.\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EOrganizers:\u003C\/strong\u003E Prasad Tetali and Santosh Vempala (GA Tech)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAgenda\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EApril 8: ARC Distinguished Lecture\u003C\/strong\u003E\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003E3:00 pm \u003Cstrong\u003EAvrim Blum,\u003C\/strong\u003E (CMU): \u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/Avrim-Blum_April%208.pdf\u0022\u003EAlgorithmic Pricing\u003C\/a\u003E\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Cstrong\u003EApril 9: ARC Theory Day\u003C\/strong\u003E\u003C\/p\u003E\u003Cul\u003E\u003Cli\u003E9:15 am - Breakfast\u003C\/li\u003E\u003Cli\u003E9:50 am - Welcome by \u003Cstrong\u003EZvi Galil\u003C\/strong\u003E (CoC Dean)\u003C\/li\u003E\u003Cli\u003E10:00 am - \u003Cstrong\u003EYael Kalai\u003C\/strong\u003E, (Microsoft Research): \u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/Abstract_Yael_Kalai.pdf\u0022\u003EEfficient Error-Resilient Interactive Protocols\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003E11:15 am - \u003Cstrong\u003ERaghu Meka,\u003C\/strong\u003E (Rutgers and IAS):\u0026nbsp;\u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/Raghu-Meka_April%209.pdf\u0022\u003E Beating the Union Bound via Geometric Techniques\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003E12:15 pm - Lunch Break\u003C\/li\u003E\u003Cli\u003E1:30 pm - \u003Cstrong\u003EAnkur Moitra\u003C\/strong\u003E, (Princeton and IAS):\u0026nbsp;\u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/Ankur-Moitra_April%209.pdf\u0022\u003E An Information Complexity Approach to\u0026nbsp; Extended Formulations\u003C\/a\u003E\u003C\/li\u003E\u003Cli\u003E2:45 pm - \u003Cstrong\u003EThomas\u003C\/strong\u003E \u003Cstrong\u003ERothvoss,\u003C\/strong\u003E (MIT): \u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/Thomas-Rothvoss_April9.pdf\u0022\u003EApproximating Bin Packing within O(log OPT * log log OPT) bins\u0026nbsp;\u003C\/a\u003E\u003C\/li\u003E\u003C\/ul\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.arc.gatech.edu\/sites\/arc.gatech.edu\/files\/ARC%20Theory%20Day%202013%20Poster.pdf\u0022\u003EPoster [PDF]\u0026nbsp;\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-02-12 14:58:16","changed_gmt":"2016-10-08 02:02:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-09T09:00:00-04:00","event_time_end":"2013-04-09T17:30:00-04:00","event_time_end_last":"2013-04-09T17:30:00-04:00","gmt_time_start":"2013-04-09 13:00:00","gmt_time_end":"2013-04-09 21:30:00","gmt_time_end_last":"2013-04-09 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":[],"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":""}},"191601":{"#nid":"191601","#data":{"type":"event","title":"ARC Distinguished Lecture: Avrim Blum, Carnegie Mellon University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Algorithmic Pricing\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EPricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In this talk I will discuss some particularly simple algorithms that are able to achieve surprisingly strong guarantees for a range of problems of this type.\u0026nbsp; As one example, for the problem of pricing \u0026lt;i\u0026gt;resources\u0026lt;\/i\u0026gt;, modeled as goods having an increasing marginal extraction cost to the seller, a simple approach of pricing the \u0026lt;i\u0026gt;i\u0026lt;\/i\u0026gt;th unit of each good at a value equal to the anticipated extraction cost of the \u0026lt;i\u0026gt;2i\u0026lt;\/i\u0026gt;th unit gives a constant-factor approximation to social welfare for a wide range of cost curves and for arbitrary buyer valuation functions.\u0026nbsp; I will also discuss simple algorithms with good approximation guarantees for revenue, as well as settings having an opposite character to resources, namely having economies of scale or decreasing marginal costs to the seller.\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":"2013-02-12 15:00:06","changed_gmt":"2016-10-08 02:02:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-08T16:00:00-04:00","event_time_end":"2013-04-08T16:00:00-04:00","event_time_end_last":"2013-04-08T16:00:00-04:00","gmt_time_start":"2013-04-08 20:00:00","gmt_time_end":"2013-04-08 20:00:00","gmt_time_end_last":"2013-04-08 20:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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":""}},"202711":{"#nid":"202711","#data":{"type":"event","title":"ARC Colloquium: Ricardo Restrepo, Institute of Mathematics, Universidad de Antioquia","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Frozenness threshold in random CSPs\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFreezing is a key part of the clustering phenomenon that is hypothesized by non-rigorous techniques from statistical physics. Indeed, it has been shown that for different kinds of random CSPs (coloring, SAT, xor-sat, and other families), if the constraint-density of a random CSP, F, in our family is greater than r_f then for almost every solution of F, a linear number of variables are frozen, meaning that their colours cannot be changed by a sequence of alterations in which we change o(n) variables at a time, always switching to another solution. If the constraint-density is less than r_f, then almost every solution has o(n) frozen variables.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;The understanding of clustering has led to the development of advanced heuristics such as Survey Propagation. It has been suggested that the freezing threshold is a precise algorithmic barrier.\u0026nbsp; There is reason to believe that for densities below r_f the random CSPs can be solved using very simple algorithms, while for densities above r_f one requires more sophisticated techniques in order to deal with frozen clusters.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;In this talk we will explain the current state of the art regarding the appearance of frozenness in random CSPs and we\u0027ll explain some of the tecniques used to analitically study such a phenomena.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Ricardo Restrepo presents a talk as part of the ARC Colloquium series."}],"uid":"27263","created_gmt":"2013-03-28 10:04:44","changed_gmt":"2017-04-13 21:24:03","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-04-01T14:30:00-04:00","event_time_end":"2013-04-01T15:30:00-04:00","event_time_end_last":"2013-04-01T15:30:00-04:00","gmt_time_start":"2013-04-01 18:30:00","gmt_time_end":"2013-04-01 19:30:00","gmt_time_end_last":"2013-04-01 19:30: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":"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":""}},"195591":{"#nid":"195591","#data":{"type":"event","title":"ARC Colloquium:  G\u00e1bor Braun","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Limiting linear programs through common information\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\u003Cp\u003EEfficiently optimizing linear functions over a polytope by directly solving the linear program requires a compact representation of the polytope, e.g., as an affine image of a polytope with few facets. We present an information theoretic approach for proving limits of such extension: the common information shared by the vertices and facets.\u003C\/p\u003E\u003Cp\u003EThis framework not only improves recent lower bounds on the CLIQUE polytope by Braverman and Moitra, but also provides a much simplified proof, and is stable under perturbations of the polytope.\u003C\/p\u003E\u003Cp\u003EThis is an ongoing joint work with Sebastian Pokutta.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-02-27 09:41:57","changed_gmt":"2016-10-08 02:02:46","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-03-25T14:30:00-04:00","event_time_end":"2013-03-25T14:30:00-04:00","event_time_end_last":"2013-03-25T14:30:00-04:00","gmt_time_start":"2013-03-25 18:30:00","gmt_time_end":"2013-03-25 18:30:00","gmt_time_end_last":"2013-03-25 18:30: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\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"187591":{"#nid":"187591","#data":{"type":"event","title":"ARC Colloquium, Madhur Tulsiani, Toyota Technological Institute at Chicago","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E The Complexity of Somewhat Approximation Resistant Predicates\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFor a Boolean predicate f on k variables, let \\rho(f) be the probability that a constraint of the form f(x_1,...,x_k) is satisfied by a random assignment. A predicate f is called \u0022somewhat approximation resistant\u0022 if for some constant \\tau \u0026gt; \\rho(f), given a \\tau-satisfiable instance of the Max-k-CSP(f) problem, it is NP-hard to find an assignment that strictly beats the naive algorithm that outputs a uniformly random assignment.\u003C\/p\u003E\u003Cp\u003ELet \\tau(f) denote the supremum over all \\tau for which the above holds. It is known that a predicate is somewhat approximation resistant precisely when its Fourier degree is at least 3. For such predicates, we give a characterization of the \u0022hardness gap\u0022 (\\tau(f) -\\rho(f)) up to a factor of O(k^5). We also give a similar characterization of the integrality gap for the natural SDP relaxation of Max-k-CSP after \\Omega(n) rounds of the Lasserre hierarchy.\u003C\/p\u003E\u003Cp\u003EJoint work with Subhash Khot and Pratik Worah.\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":"2013-01-29 09:27:57","changed_gmt":"2016-10-08 02:02:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-03-11T14:30:00-04:00","event_time_end":"2013-03-11T15:30:00-04:00","event_time_end_last":"2013-03-11T15:30:00-04:00","gmt_time_start":"2013-03-11 18:30:00","gmt_time_end":"2013-03-11 19:30:00","gmt_time_end_last":"2013-03-11 19: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":""}},"184781":{"#nid":"184781","#data":{"type":"event","title":"ARC Colloquium: Amin Coja-Oghlan, Goethe University, Frankfurt, Germany","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Chasing the k-SAT threshold\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003ELet F be a random Boolean formula in conjunctive normal form over n Boolean variables with m clauses of length k. The existence of a (non-uniform) sharp threshold for the satisfiability of such formulas is well known [Friedgut 1999]. However, despite considerable effort the precise location of this phase transition remains unknown for any k\u0026gt;2. The best previous upper and lower bounds differ by an additive $k\\ln 2\/2$ [Achlioptas, Peres 2003]. In this talk I present an improved lower bound, which reduces the gap to ~0.19. The proof is inspired by the cavity method of statistical mechanics.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-01-17 10:51:42","changed_gmt":"2016-10-08 02:02:10","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-03-04T12:00:00-05:00","event_time_end":"2013-03-04T12:00:00-05:00","event_time_end_last":"2013-03-04T12:00:00-05:00","gmt_time_start":"2013-03-04 17:00:00","gmt_time_end":"2013-03-04 17:00:00","gmt_time_end_last":"2013-03-04 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"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":""}},"191481":{"#nid":"191481","#data":{"type":"event","title":"ARC Colloquium: Gil Kalai, Hebrew University of Jerusalem- Israel\/Yale University - New Haven, CT","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E: Probability and Algorithms - Examples of open collaborative research over the Internet\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;I shall discuss examples of recent Internet research oriented math activities:\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;1) Polymath5 - Erdos discrepancy problem.\u003C\/p\u003E\u003Cp\u003EThe problem is to find a function from the natural numbers to {-1,1} such that the sum of values on any sequence of the form {a,2,3a,...,ra} is bounded. Erdos conjectured that no such function exists. It is still open even after many individual attempts and an attempt to solve it collectively in a polymath project.\u003C\/p\u003E\u003Cp\u003EBackground: please look at this MO problem\u003C\/p\u003E\u003Cp\u003E\u003Ca href=\u0022http:\/\/mathoverflow.net\/questions\/105383\/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem\u0022\u003Ehttp:\/\/mathoverflow.net\/questions\/105383\/the-behavior-of-a-certain-greedy-algorithm-for-erds-discrepancy-problem\u003C\/a\u003E \u0026nbsp;(and the blog post linked there.)\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;2) The study of Mobius randomness over blogs and MathOverflow.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;A function defined on the natural number is Mobius-random if its correlation with the Mobius function tends to zero. The prime number theorem asserts that the constant one function is Mobius random. I will discuss the result by Ben Green that functions described by bounded depth circuits are Mobius-random.\u003C\/p\u003E\u003Cp\u003EHere is one link\u003C\/p\u003E\u003Cp\u003EMO posts: \u003Ca href=\u0022http:\/\/mathoverflow.net\/questions\/57543\/walsh-fourier-transform-of-the-mobius-function\u0022\u003Ehttp:\/\/mathoverflow.net\/questions\/57543\/walsh-fourier-transform-of-the-mobius-function\u003C\/a\u003E, which contains more links.\u003C\/p\u003E\u003Cp\u003EI may briefly mention a couple more examples. One is my debate with Aram Harrow on the feasibility of quantum computers. It took place over the blog \u0022Goedel\u0027s lost letter and NP=P\u0022 (The\u0026nbsp;\u003Cstrong\u003E\u003Ca href=\u0022http:\/\/rjlipton.wordpress.com\/2012\/01\/30\/perpetual-motion-of-the-21st-century\/\u0022 target=\u0022_blank\u0022\u003Efirst post\u003C\/a\u003E\u003C\/strong\u003E\u0026nbsp;the\u0026nbsp;\u003Cstrong\u003E\u003Ca href=\u0022http:\/\/rjlipton.wordpress.com\/2012\/10\/03\/quantum-supremacy-or-classical-control\/\u0022 target=\u0022_blank\u0022\u003Elast post\u003C\/a\u003E\u003C\/strong\u003E\u003Cstrong\u003E\u0026nbsp;)\u003C\/strong\u003E\u0026nbsp;and the other is probability-motivated questions regarding the computer game \u0022angry birds\u0022.\u003C\/p\u003E\u003Cp\u003EI will try to give some taste of the mathematical problems\/issues and also a little taste of this way of \u0022doing mathematics\u0022.\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":"2013-02-12 12:52:20","changed_gmt":"2016-10-08 02:02:33","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-02-25T12:00:00-05:00","event_time_end":"2013-02-25T12:00:00-05:00","event_time_end_last":"2013-02-25T12:00:00-05:00","gmt_time_start":"2013-02-25 17:00:00","gmt_time_end":"2013-02-25 17:00:00","gmt_time_end_last":"2013-02-25 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":[],"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":""}},"192671":{"#nid":"192671","#data":{"type":"event","title":"CS: Spectral Algorithms Guest Lecture by Ravi Kannan, Microsoft Research India","body":[{"value":"\u003Cp\u003ESpectral Algorithms: \u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~vempala\/spectral\/course.html\u0022\u003Ehttp:\/\/www.cc.gatech.edu\/~vempala\/spectral\/course.html\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-02-18 11:21:17","changed_gmt":"2016-10-08 02:02:37","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-02-21T08:30:00-05:00","event_time_end":"2013-02-21T10:00:00-05:00","event_time_end_last":"2013-02-21T10:00:00-05:00","gmt_time_start":"2013-02-21 13:30:00","gmt_time_end":"2013-02-21 15:00:00","gmt_time_end_last":"2013-02-21 15:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"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:vempala@cc.gatech.edu\u0022\u003Evempala@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"192661":{"#nid":"192661","#data":{"type":"event","title":"CS: Spectral Algorithms Guest Lecture by Ravi Kannan, Microsoft Research India","body":[{"value":"\u003Cp\u003ESpectral Algorithms:\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~vempala\/spectral\/course.html\u0022\u003Ehttp:\/\/www.cc.gatech.edu\/~vempala\/spectral\/course.html\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":"2013-02-18 11:05:37","changed_gmt":"2016-10-08 02:02:37","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-02-19T08:30:00-05:00","event_time_end":"2013-02-19T10:00:00-05:00","event_time_end_last":"2013-02-19T10:00:00-05:00","gmt_time_start":"2013-02-19 13:30:00","gmt_time_end":"2013-02-19 15:00:00","gmt_time_end_last":"2013-02-19 15: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:vempala@cc.gatech.edu\u0022\u003Evempala@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}},"187121":{"#nid":"187121","#data":{"type":"event","title":"ARC Colloquium: Debmalya Panigrahi, Microsoft Research","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EEnergy-efficient Scheduling in the Non-clairvoyant model\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EA fundamental problem in energy-efficient computing is to schedule multiple jobs released over time on a single machine with adjustable speed so as to minimize the sum of flowtime and energy. Note that the two objectives are in conflict: higher speeds reduce flowtime at the cost of increased energy consumption. In the clairvoyant version of the problem, the parameters of a job (volume and density) are revealed when the job is released. For this problem, a series of results culminated in a (2+epsilon)-competitive algorithm due to Bansal, Chan, and Pruhs. In this talk, I will consider the non-clairvoyant version of the problem where the density of a job is revealed on release but the volume is unknown. This version is often more practical and has been widely considered in other scheduling problems. We give a constant-competitive algorithm, which to the best of our knowledge, is the first non-trivial result for this problem.\u003C\/p\u003E\u003Cp\u003EOur algorithm is defined by simulating the clairvoyant algorithm in a novel inductive way, which then leads to an inductive analytical tool that may be of independent interest for other non-clairvoyant scheduling problems.\u003C\/p\u003E\u003Cp\u003E(Based on joint work with Yossi Azar, Nikhil Devanur, and Zhiyi Huang.)\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27263","created_gmt":"2013-01-28 09:50:51","changed_gmt":"2016-10-08 02:02:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-02-18T12:00:00-05:00","event_time_end":"2013-02-18T12:00:00-05:00","event_time_end_last":"2013-02-18T12:00:00-05:00","gmt_time_start":"2013-02-18 17:00:00","gmt_time_end":"2013-02-18 17:00:00","gmt_time_end_last":"2013-02-18 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":[],"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":""}},"188251":{"#nid":"188251","#data":{"type":"event","title":"ARC Colloquium: Balasubramanian Sivan, University of Wisconsin-Madison","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: \u003C\/strong\u003EPrior Robust Optimization\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe focus of this talk is optimization in the presence of uncertain inputs.\u0026nbsp; We model uncertainty as input being drawn from one among a large known class of distributions, however the specific distribution is unknown to the algorithm. The goal is to develop a single algorithm that for every distribution in this class, performs approximately as well as the optimal algorithm tailored for that specific distribution. Such algorithms are robust to assumptions on prior\u003Cbr \/\u003Edistributions and are good candidates for deployment in real systems.\u003C\/p\u003E\u003Cp\u003EIn this talk, we present general techniques for developing prior robust algorithms for two distinct lines of research --- online algorithms and mechanism design. In online algorithms, we present our results for a very general class of resource allocation problems with several applications, including to internet advertising. We develop a simple-to-implement prior robust algorithm with near optimal profit guarantee. Our algorithm has been deployed globally along with Microsoft MSN\u0027s display ads serving engine.\u0026nbsp; In mechanism design, we focus on the well studied makespan minimization problem in machine scheduling. Here, our goal is to schedule jobs with stochastic runtimes on machines which are operated by strategic agents who hold the runtimes private. We design simple-to-implement truthful prior robust mechanisms that under different distributional assumptions provide constant and sub-logarithmic approximations to expected makespan.\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":"2013-01-30 16:56:44","changed_gmt":"2016-10-08 02:02:19","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-02-04T12:00:00-05:00","event_time_end":"2013-02-04T12:00:00-05:00","event_time_end_last":"2013-02-04T12:00:00-05:00","gmt_time_start":"2013-02-04 17:00:00","gmt_time_end":"2013-02-04 17:00:00","gmt_time_end_last":"2013-02-04 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":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}},"181911":{"#nid":"181911","#data":{"type":"event","title":"ARC Colloquium: Sanjeev Arora, Princeton University","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: Is Machine Learning Tractable? --- Three Vignettes\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMany tasks in machine learning (especially unsupervised learning) are provably intractable: NP-hard or worse. Nevertheless, researchers have developed heuristic algorithms to solve these tasks in practice. In most cases, there are no\u0026nbsp; provable guarantees on the performance of these algorithms\/heuristics ---neither on their running time, nor on the quality of solutions they return.\u0026nbsp; Can we change this state of affairs?\u003C\/p\u003E\u003Cp\u003EThis talk will suggest that the answer is yes, and cover three recent works as illustration. (a) A new algorithm for learning topic models.\u003C\/p\u003E\u003Cp\u003EThis concerns a new algorithm for topic models (including the Linear Dirichlet Allocations of Blei et al. but also works for more general models) that provably works in theory under some reasonable assumptions and is also up to 50 times faster than existing software in practice. It relies upon a new procedure for nonnegative matrix factorization. (b) What classifiers are worth learning? (c) Provable ICA with unknown gaussian noise. \u003Cbr \/\u003E(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant Sachdeva.)\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":"Is Machine Learning Tractable? --- Three Vignettes"}],"uid":"27263","created_gmt":"2013-01-09 13:21:58","changed_gmt":"2016-10-08 02:01:55","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2013-01-14T12:00:00-05:00","event_time_end":"2013-01-14T12:00:00-05:00","event_time_end_last":"2013-01-14T12:00:00-05:00","gmt_time_start":"2013-01-14 17:00:00","gmt_time_end":"2013-01-14 17:00:00","gmt_time_end_last":"2013-01-14 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":""}}}