Seminars and Colloquia by Series

Theory Day Speaker 1 - What Makes an Algorithm Great?

Series
Other Talks
Time
Saturday, October 24, 2009 - 12:30 for 2 hours
Location
LeCraw Auditorium
Speaker
Richard KarpElectrical Engineering and Computer Sciences, University of California, Berkeley
From time to time a new algorithm comes along that causes a sensation in theoretical computer science or in an area of application because of its resolution of a long-standing open question, its surprising efficiency, its practical usefulness, the novelty of its setting or approach, the elegance of its structure, the subtlety of its analysis or its range of applications. We will give examples of algorithms that qualify for greatness for one or more of these reasons, and discuss how to equip students to appreciate them and understand their strengths and weaknesses.

Random regular graphs: from spectrum to geometry and back

Series
ACO Seminar
Time
Friday, October 23, 2009 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Eyal LubetzkyMicrosoft Research, Redmond, WA
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.

Introduction to Heegaard Floer Homology

Series
Geometry Topology Working Seminar
Time
Friday, October 23, 2009 - 15:00 for 2 hours
Location
Skiles 269
Speaker
Amey KalotiGeorgia Tech

Please Note: This is a 2 hour talk.

Abstract: Heegaard floer homology is an invariant of closed 3 manifolds defined by Peter Ozsvath and Zoltan Szabo. It has proven to be a very strong invariant of 3 manifolds with connections to contact topology. In these talks we will try to define the Heegaard Floer homology without assuming much background in low dimensional topology. One more goal is to present the combinatorial description for this theory.

From transfinite diameter to order-density to best-packing: the asymptotics of ground state configurations

Series
Analysis Seminar
Time
Friday, October 23, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Doug HardinVanderbilt University
I will review recent and classical results concerning the asymptotic properties (as N --> \infty) of 'ground state' configurations of N particles restricted to a d-dimensional compact set A\subset {\bf R}^p that minimize the Riesz s-energy functional \sum_{i\neq j}\frac{1}{|x_{i}-x_{j}|^{s}} for s>0. Specifically, we will discuss the following (1) For s < d, the ground state configurations have limit distribution as N --> \infty given by the equilibrium measure \mu_s, while the first order asymptotic growth of the energy of these configurations is given by the 'transfinite diameter' of A. (2) We study the behavior of \mu_s as s approaches the critical value d (for s\ge d, there is no equilibrium measure). In the case that A is a fractal, the notion of 'order two density' introduced by Bedford and Fisher naturally arises. This is joint work with M. Calef. (3) As s --> \infty, ground state configurations approach best-packing configurations on A. In work with S. Borodachov and E. Saff we show that such configurations are asymptotically uniformly distributed on A.

Interacting particles, series Jackson networks, and non-crossing probabilities

Series
Stochastics Seminar
Time
Thursday, October 22, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Ton Dieker(ISyE, Georgia Tech)
In this talk, we study an interacting particle system arising in the context of series Jackson queueing networks. Using effectively nothing more than the Cauchy-Binet identity, which is a standard tool in random-matrix theory, we show that its transition probabilities can be written as a signed sum of non-crossing probabilities. Thus, questions on time-dependent queueing behavior are translated to questions on non-crossing probabilities. To illustrate the use of this connection, we prove that the relaxation time (i.e., the reciprocal of the ’spectral gap’) of a positive recurrent system equals the relaxation time of a single M/M/1 queue with the same arrival and service rates as the network’s bottleneck station. This resolves a 1985 conjecture from Blanc on series Jackson networks. Joint work with Jon Warren, University of Warwick.

Jacobians of Nearly Complete Graphs

Series
Graph Theory Seminar
Time
Thursday, October 22, 2009 - 12:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Peter WhalenMath, GT
The Jacobian of a graph, also known as the Picard Group, Sandpile Group, or Critical Group, is a discrete analogue of the Jacobian of an algebraic curve. It is known that the order of the Jacobian of a graph is equal to its number of spanning trees, but the exact structure is known for only a few classes of graphs. In this talk I will present a combinatorial method of approaching the Jacobian of graphs by way of a chip-firing game played on its vertices. We then apply this chip-firing game to explicitly characterize the Jacobian of nearly complete graphs, those obtained from the complete graph by deleting either a cycle or two vertex-disjoint paths incident with all but one vertex. This is joint work with Sergey Norin.

Theory and Applications of Model Equations for Surface Water Waves

Series
School of Mathematics Colloquium
Time
Thursday, October 22, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Jerry BonaUniversity of Illinois at Chicago
After a brief account of some of the history of this classical subject, we indicate how such models are derived. Rigorous theory justifying the models will be discussed and the conversation will then turn to some applications. These will be drawn from questions arising in geophysics and coastal engineering, as time permits.

Inequalities for Derivatives and their Applications

Series
Analysis Seminar
Time
Wednesday, October 21, 2009 - 14:00 for 8 hours (full day)
Location
Skiles 269
Speaker
Yuliya BabenkoSam Houston State University
In this talk we will discuss Kolmogorov and Landau type inequalities for the derivatives. These are the inequalities which estimate the norm of the intermediate derivative of a function (defined on an interval, R_+, R, or their multivariate analogs) from some class in terms of the norm of the function itself and norm of its highest derivative. We shall present several new results on sharp inequalities of this type for special classes of functions (multiply monotone and absolutely monotone) and sequences. We will also highlight some of the techniques involved in the proofs (comparison theorems) and discuss several applications.

ARC-ACO Colloquium - Concentration under Heavy Tails

Series
Other Talks
Time
Wednesday, October 21, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Klaus, Room 1116
Speaker
Ravi KannanMicrosoft Research Labs, Bangalore India

Please Note: Tea and light refreshments 1:30 in Room 2222. Organizer: Santosh Vempala

Concentration results for the TSP, MWST and many other problems with random inputs show the answer is concentrated tightly around the mean. But most results assume uniform density of the input. We will generalize these to heavy-tailed inputs which seem to be ubiquitous in modern applications. To accomplish this, we prove two new general probability inequalities. The simpler first inequality weakens both hypotheses in Hoffding-Azuma inequality and is enough to tackle TSP, MWST and Random Projections. The second inequality further weakens the moment requirements and using it, we prove the best possible concentration for the long-studied bin packing problem as well as some others. Many other applications seem possible..

Pages