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.
Monday, August 29, 2011 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Amit Einav – School of Mathematics, Georgia Tech
The presented work deals with two distinct problems in the field
of Mathematical Physics, and as such will have two parts addressing each
problem.
The first part is dedicated to an 'almost' solution of Villani's conjecture,
a known conjecture related to a Statistical Mechanics model invented by Kac
in 1956, giving a rigorous explanation of some simple cases of the Boltzman
equation. In 2003 Villani conjectured that the time it will take the system
of particles in Kac's model to equalibriate is proportional to the number of
particles in the system. Our main result in this part is an 'almost proof'
of that conjecture, showing that for all practical purposes we can consider
it to be true.
The second part of the presentation is dedicated to a newly developed trace
inequality for the fractional Laplacian, connecting between the fractional
Laplacian of a function and its restriction to the intersection of the
hyperplanes x_n =...= x_n-j+1 = 0 , where 1 <= j < n.
The newly found inequality is
sharp and the functions that attain inequality in it are completely
classified.
Thursday, August 25, 2011 - 11:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Kamal Jain – Microsoft Research, Redmond, WA
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.
Monday, August 22, 2011 - 10:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 114
Speaker
TBA – TBA
The main focus of this working seminar for this semester will be the mathematics of RNA folding, beginning with some historical context. See www.math.gatech.edu/~heitsch/dmbws.html for further information on possible topics and papers. No meeting this week; regular meetings will start on August 29. If interested please email the organizer.
Ricardo Restrepo Lopez – School of Mathematics, Georgia Tech
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.
Shape optimization is the study of optimization problems whose
unknown is a domain in R^d. The seminar is focused on the understanding
of the case where admissible shapes are required to be convex. Such
problems arises in various field of applied mathematics, but also in
open questions of pure mathematics. We propose an analytical study of
the problem.
In the case of 2-dimensional shapes, we show some results for a large
class of functionals, involving geometric functionals, as well as
energies involving PDE. In particular, we give some conditions so that
solutions are polygons. We also give results in higher dimension,
concerned with the Mahler conjecture in convex geometry and the
Polya-Szego conjecture in potential theory. We particularly make the
link with the so-called Brunn-Minkowsky inequalities.
Wednesday, June 15, 2011 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 05
Speaker
Dr Anna Maltsev – University of Bonn
We consider ensembles of $N \times N$ Hermitian Wigner matrices, whose entries are (up to the symmetry constraints) independent and identically distributed random variables. Assuming sufficient regularity for the probability density function of the entries, we show that the expectation of the density of states on arbitrarily small intervals converges to the semicircle law, as $N$ tends to infinity.