Georgia Institute of Technology College of Sciences

I will discuss a computation of the lower central series of the Torelli group as a symplectic module, which depends on some conjectures and was performed 15 years ago in unpublished joint work with Ezra Getzler. Renewed interest in this computation comes from recent work of Benson Farb on representation stability.

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.

In this work we provide several improvements in the study of phase transitions of interacting particle systems: 1. We determine a quantitative relation between non-extremality of the limiting Gibbs measure of a tree-based spin system, and the temporal mixing of the Glauber Dynamics over its finite projections. We define the concept of `sensitivity' of a reconstruction scheme to establish such a relation. In particular, we focus in the independent sets model, determining a phase transition for the mixing time of the Glauber dynamics at the same location of the extremality threshold of the simple invariant Gibbs version of the model. 2. We develop the technical analysis of the so-called spatial mixing conditions for interacting particle systems to account for the connectivity structure of the underlying graph. This analysis leads to improvements regarding the location of the uniqueness/non-uniqueness phase transition for the independent sets model over amenable graphs; among them, the elusive hard-square model in lattice statistics, which has received attention since Baxter's solution of the analogue hard-hexagon in 1980. 3. We build on the work of Montanari and Gerschenfeld to determine the existence of correlations for the coloring model in sparse random graphs. In particular, we prove that correlations exist above the `clustering' threshold of such model; thus providing further evidence for the conjectural algorithmic `hardness' occurring at such point.