Seminars and Colloquia by Series

Series: ACO Seminar
Thursday, August 25, 2011 - 11:05 , Location: Skiles 006 , Kamal Jain , Microsoft Research, Redmond, WA , Organizer: Prasad Tetali
I will present two related 30-minute talks. Title 1: Generalized Online Matching with Concave Utilities Abstract 1: In this talk we consider a search engine's ad matching problem with soft budget. In this problem, there are two sides. One side is ad slots and the other is advertisers. Currently advertisers are modeled to have hard budget, i.e., they have full utility for ad slots until they reach their budget, and at that point they can't be assigned any more ad-slots. Mehta-Saberi-Vazirani-Vazirani and Buchbinder-J-Naor gave a 1-1/e approximation algorithm for this problem, the latter had a traditional primal-dual analysis of the algorithm. In this talk, we consider a situation when the budgets are soft. This is a natural situation if one models that the cost of capital is convex or the amount of risk is convex. Having soft budget makes the linear programming relaxation as a more general convex programming relaxation. We still adapt the primal-dual schema to this convex program using an elementary notion of convex duality. The approximation factor is then described as a first order non-linear differential equation, which has at least 1-1/e as its solution. In many cases one can solve these differential equations analytically and in some cases numerically to get algorithms with factor better than 1-1/e. Based on two separate  joint works, one  with Niv Buchbinder and Seffi Naor, and the other with Nikhil Devanur.  Title 2: Understanding Karp-Vazirani-Vazirani's Online Matching (1990) via Randomized Primal-Dual. Abstract 2: KVV online matching algorithm is one of the most beautiful online algorithms. The algorithm is simple though its analysis is not equally simple. Some simpler version of analysis are developed over the last few years. Though, a mathematical curiosity still remains of understanding what is happening behind the curtains, which  has made extending the KVV algorithm hard to apply to other problems, or even applying to the more general versions of online matching itself. In this talk I will present one possibility of lifting the curtains. We develop a randomized version of Primal-Dual schema and redevelop KVV algorithm within this framework. I will then show how this framework makes extending KVV algorithm to vertex weighted version essentially trivial, which is currently done through a lot of hard work in a brilliant paper of Aggarwal-Goel-Karande-Mehta (2010). Randomized version of Primal-Dual schema was also a missing technique from our toolbox of algorithmic techniques. So this talk also fills that gap.
Series: ACO Seminar
Tuesday, March 15, 2011 - 16:30 , Location: Klaus 2443 , Balaji Prabhakar , Stanford University , Organizer: Robin Thomas
Why did kamikaze pilots wear helmets? Why does glue not stick to the inside of the bottle? Why is lemonade made with artificial flavor but dishwashing liquid made with real lemons? How can I avoid traffic jams and be paid for it? While the first three are some of life's enduring questions, the fourth is the subject of a traffic decongestion research project at Stanford University. In this talk, I will briefly describe this project and, more generally, discuss incentive mechanisms for Societal Networks--- networks which are vital for a society's functioning; for example, transportation, energy, healthcare and waste management. I will talk about incentive mechanisms and experiments for reducing road congestion, pollution and energy use, and for improving "wellness" and good driving habits. Some salient themes are: using low-cost sensing technology to make societal networks much more efficient, using price as a signal to co-ordinate individual behavior, and intelligently "throwing money at problems".
Series: ACO Seminar
Tuesday, March 8, 2011 - 16:30 , Location: KACB 1116 , Greg Valiant , University of California, Berkeley , Organizer: Robin Thomas
Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. This problem has a rich history of study in both statistics and, more recently, in CS Theory and Machine Learning. We present a polynomial time algorithm for this problem (running time, and data requirement polynomial in the dimension and the inverse of the desired accuracy), with provably minimal assumptions on the Gaussians. Prior to this work, it was unresolved whether such an algorithm was even information theoretically possible (ie, whether a polynomial amount of data, and unbounded computational power sufficed). One component of the proof is showing that noisy estimates of the low-order moments of a 1-dimensional mixture suffice to recover accurate estimates of the mixture parameters, as conjectured by Pearson (1894), and in fact these estimates converge at an inverse polynomial rate. The second component of the proof is a dimension-reduction argument for how one can piece together information from different 1-dimensional projections to yield accurate parameters.
Series: ACO Seminar
Thursday, February 24, 2011 - 16:30 , Location: KACB 1116B , Aranyak Mehta , Google Research , Organizer: Robin Thomas
The spectacular success of search and display advertising -- to businesses and search engine companies -- and its huge growth potential has attracted the attention of researchers from many aspects of computer science. Since a core problem in this area is that of effective ad allocation, an inherently algorithmic and game-theoretic question, numerous theoreticians have worked in this area in recent years. Ad allocation involves matching ad slots to advertisers, under demand and supply constraints. In short, the better the matching, the more efficient the market. Interestingly, the seminal work on online matching, by Karp, Vazirani and Vazirani, was done over two decades ago, well before the advent of the Internet economy! In this talk, I will give an overview of several key algorithmic papers in this area, starting with its purely academic beginnings, to papers that actually address the Adwords problem. The elegant -- and deep -- theory behind these algorithms involves new combinatorial, probabilistic and linear programming techniques. Besides the classic KVV paper (STOC 1990), this talk will refer to several papers with my co-authors: Mehta, Saberi, Vazirani, Vazirani (FOCS 05, J. ACM 07), Goel, Mehta (SODA 08), Feldman, Mehta, Mirrokni, Muthukrishnan (FOCS 09), Aggarwal, Goel, Karande, Mehta (SODA 10), Karande, Mehta, Tripathi (STOC 11).
Series: ACO Seminar
Thursday, January 13, 2011 - 15:05 , Location: Skiles 154 , Sergey Norin , Princeton University , Organizer: Robin Thomas
A well-known conjecture of Lovasz and Plummer asserts that the number of perfect matchings in 2-edge-connected cubic graph is exponential in the number of vertices. Voorhoeve has shown in 1979 that the conjecture holds for bipartite graphs, and Chudnovsky and Seymour have recently shown that it holds for planar graphs. In general case, however, the best known lower bound has been until now barely super-linear. In this talk we sketch a proof of the conjecture. The main non-elementary ingredient of the proof is Edmonds' perfect matching polytope theorem. This is joint work with Louis Esperet, Frantisek Kardos, Andrew King and Daniel Kral.
Series: ACO Seminar
Thursday, October 28, 2010 - 16:30 , Location: Skiles 255 , Bertrand Guenin , Dept. of Combinatorics and Optimization, University of Waterloo , Organizer: Robin Thomas
A signed graph is a pair (G, \Sigma) where G is a graph and \Sigma is a subset of the edges of G. A cycle C in G is even (resp. odd) if E(C) \cap \Sigma is even (resp. odd). A blocking pair in a signed graph is a pair of vertices {x, y} such that every odd cycle in (G, \Sigma) intersects at least one of the vertices x and y. Blocking pairs arise in a natural way in the study of even cycle matroids on signed graphs as well as signed graphs with no odd K_5 minor. In this article, we characterize when the blocking pairs of a signed graph can be represented by 2-cuts in an auxiliary graph. We discuss the relevance of this result to the problem of characterizing signed graphs with no odd K_5 minor and determing when two signed graphs represent the same even cycle matroid. This is joint work with Irene Pivotto and Paul Wollan.
Series: ACO Seminar
Friday, October 22, 2010 - 15:05 , Location: Skiles 255 , Jacob Fox , Mathematics, MIT , Organizer: Prasad Tetali
We describe a simple and yet surprisingly powerful probabilistic technique which shows how to find in a dense graph a large subset of vertices in which all (or almost all) small subsets have many common neighbors. Recently this technique has had several striking applications to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In this talk, which is based on a survey with Benny Sudakov, we discuss some of these applications. 
Series: ACO Seminar
Tuesday, May 4, 2010 - 16:00 , Location: Klaus 1116W , Nikhil Devanur , Microsoft Research , Organizer:

Hosted by Vijay Vazirani

I will talk about new results on convex programs and distributed algorithms for Fisher markets with linear and spending constraint utilities. In particular: (i) show a new convex program for the linear utilities case of Fisher markets. This program easily extends to the case of spending constraint utilities as well, thus resolving an open question raised by Vazirani; (ii) show that the gradient descent algorithm with respect to a Bregman divergence converges with rate O(1/t) under a condition that is weaker than having Lipschitz continuous gradient (which is the usual assumption in the optimization literature for obtaining the same rate); (iii) show that the Proportional Response dynamics recently introduced by Zhang is equivalent to a gradient descent algorithm for solving the new convex program. This insight also gives us better convergence rates, and helps us generalize it to spending constraint utilities.
Series: ACO Seminar
Thursday, March 11, 2010 - 16:30 , Location: Skiles 255 , Lisa Fleischer , Professor, Dartmouth College , Organizer: Prasad Tetali
We look at problems of scheduling jobs to machines when the processing time of a job is machine dependent.  Common objectives in this framework are to minimize the maximum load on a machine, or to minimize the average completion time of jobs.  These are well-studied problems.  We consider the related problem of trying to select a subset of machines to use to minimize machine costs subject to bounds on the maximum load or average completion time of the corresponding schedule.  These problems are NP-hard and include set-cover as a special case.  Thus we focus on approximation algorithms and get tight, or almost tight approximation guarantees. A key part of our results depends on showing the submodularity of the objective of a related optimization problem.
Series: ACO Seminar
Friday, October 23, 2009 - 15:05 , Location: Skiles 255 , Eyal Lubetzky , Microsoft Research, Redmond, WA , Organizer: Prasad Tetali
The class of random regular graphs has been the focus of extensive study highlighting the excellent expansion properties of its typical instance. For instance, it is well known that almost every regular graph of fixed degree is essentially Ramanujan, and understanding this class of graphs sheds light on the general behavior of expanders. In this talk we will present several recent results on random regular graphs, focusing on the interplay between their spectrum and geometry. We will first discuss the relation between spectral properties and the abrupt convergence of the simple random walk to equilibrium, derived from precise asymptotics of the number of paths between vertices. Following the study of the graph geometry we proceed to its random perturbation via exponential weights on the edges (first-passage-percolation). We then show how this allows the derivation of various properties of the classical Erd\H{o}s-R\'enyi random graph near criticality. Finally, returning to the spectrum of random regular graph, we discuss the question of how close they really are to being Ramanujan and conclude with related problems involving random matrices. Based on joint works with Jian Ding, Jeong Han Kim and Yuval Peres, with Allan Sly and with Benny Sudakov and Van Vu.

Pages