Seminars and Colloquia by Series

The Adwords problem under random permutations

Series
ACO Seminar
Time
Wednesday, March 11, 2009 - 16:00 for 1 hour (actually 50 minutes)
Location
Klaus 2100
Speaker
Nikhil DevanurMicrosoft Research
We consider the problem of a search engine trying to assign a sequence of search keywords to a set of competing bidders, each with a daily spending limit. The goal is to maximize the revenue generated by these keyword sales, bearing in mind that, as some bidders may eventually exceed their budget, not all keywords should be sold to the highest bidder. We assume that the sequence of keywords (or equivalently, of bids) is revealed on-line. Our concern will be the competitive ratio for this problem versus the off-line optimum. We extend the current literature on this problem by considering the setting where the keywords arrive in a random order. In this setting we are able to achieve a competitive ratio of 1-\epsilon under some mild, but necessary, assumptions. In contrast, it is already known that when the keywords arrive in an adversarial order, the best competitive ratio is bounded away from 1. Our algorithm is motivated by PAC learning, and proceeds in two parts: a training phase, and an exploitation phase. Joint work with Tom Hayes, UNM.

PDE Techniques in Wavelet Transforms and Applications Image Processing

Series
Research Horizons Seminar
Time
Wednesday, March 11, 2009 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Hao Min ZhouSchool of Mathematics, Georgia Tech
In this talk, I will present an brief introdution to use partial differential equation (PDE) and variational techniques (including techniques developed in computational fluid dynamics (CFD)) into wavelet transforms and Applications in Image Processing. Two different approaches are used as examples. One is PDE and variational frameworks for image reconstruction. The other one is an adaptive ENO wavelet transform designed by using ideas from Essentially Non-Oscillatory (ENO) schemes for numerical shock capturing.

"Feel Sick? Follow the money!" - New Perspectives on Global Human Mobility and Disease Dynamics

Series
Mathematical Biology Seminar
Time
Wednesday, March 11, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Dirk BrockmannNorthwestern University
Human Mobility in our globalised world has reached a complexity and volume of unprecedented degree. More than 60 million people travel billions of kilometres on more than 2 million international flights each week. Hundreds of millions of people commute on a complex web of highways and railroads most of which operate at their maximum capacity. Human mobility is responsible for the geographical spread of emergent human infectious diseases and plays a key role in human mediated bioinvasion, the dominant factor in the global biodiversity crisis. I will report on the recent discovery of scaling laws in global human traffic (obtained from online bill-tracking at www.wheresgeorge.com) and mathematical models that can account for it. I will present a complex network perspective on multi-scale human traffic networks, report on their statistical properties and show that they can be used to identify geographically coherent communities that only vaguely resemble administrative ones. The approach provides an operational segmentation of maps into a hierarchical set of effective regions and boundaries based on human behavior. I will briefly talk about European transportation networks, geocaching and trackable items.

Tolerance Graphs and Orders

Series
Combinatorics Seminar
Time
Wednesday, March 11, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Ann TrenkDepartment of Mathematics, Wellesley College
Tolerance graphs were introduced in 1982 by Golumbic and Monma as a generalization of the class of interval graphs. A graph G= (V, E) is an interval graph if each vertex v \in V can be assigned a real interval I_v so that xy \in E(G) iff I_x \cap I_y \neq \emptyset. Interval graphs are important both because they arise in a variety of applications and also because some well-known recognition problems that are NP-complete for general graphs can be solved in polynomial time when restricted to the class of interval graphs. In certain applications it can be useful to allow a representation of a graph using real intervals in which there can be some overlap between the intervals assigned to non-adjacent vertices. This motivates the following definition: a graph G= (V, E) is a tolerance graph if each vertex v \in V can be assigned a real interval I_v and a positive tolerance t_v \in {\bf R} so that xy \in E(G) iff |I_x \cap I_y| \ge \min\{t_x,t_y\}. These topics can also be studied from the perspective of ordered sets, giving rise to the classes of Interval Orders and Tolerance Orders. In this talk we give an overview of work done in tolerance graphs and orders . We use hierarchy diagrams and geometric arguments as unifying themes.

Classical solutions in Hölder and Sobolev spaces for the thin film equation

Series
PDE Seminar
Time
Tuesday, March 10, 2009 - 15:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Hans KnüpferCourant Institute, New York
We consider the the following fourth order degenerate parabolic equation h_t + (hh_xxx)_x = 0. The equation arises in the lubrication approximation regime, describing the spreading of a thin film liquid with height profile h >= 0 on a plate. We consider the equation as free boundary problem, defined on its positivity set. We address existence and regularity of classical solutions in weighted Hölder and Sobolev spaces.

Fluctuation Theorems

Series
CDSNS Colloquium
Time
Monday, March 9, 2009 - 16:30 for 2 hours
Location
Skiles 255
Speaker
Mark PollicottUniversity of Warwick
The Cohen-Gallavotti Fluctuation theorem is a result describing the behaviour of simple hyperbolic dynamical systems. It was introduced to illustrate, in a somewhat simpler context, anomalies in the second law of thermodynamics. I will describe the mathematical formulation of this Fluctuation Theorem, and some variations on it.

Recent Progresses and Challenges in High-Order Unstructured Grid Methods in CFD

Series
Applied and Computational Mathematics Seminar
Time
Monday, March 9, 2009 - 13:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Zhi J. WangAerospace Engineering, Iowa State University
The current breakthrough in computational fluid dynamics (CFD) is the emergence of unstructured grid based high-order (order > 2) methods. The leader is arguably the discontinuous Galerkin method, amongst several other methods including the multi-domain spectral, spectral volume (SV), and spectral difference (SD) methods. All these methods possess the following properties: k-exactness on arbitrary grids, and compactness, which is especially important for parallel computing. In this talk, recent progresses in the DG, SV, SD and a unified formulation called lifting collocation penalty will be presented. Numerical simulations with the SV and the SD methods will be presented. The talk will conclude with several remaining challenges in the research on high-order methods.

Invariants of Legendrian Knots from Open Book Decompositions

Series
Geometry Topology Seminar
Time
Monday, March 9, 2009 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Sinem OnaranSchool of Mathematics, Georgia Tech
Given any contact 3-manifold, Etnyre and Ozbagci defined new invariants of the contact structures in terms of open book decompositions supporting the contact structure. One of the invariants is the support genus of the contact structure which is defined as the minimal genus of a page of an open book that supports the contact structure. In a similar fashion, we define the support genus sg(L) of a Legendrian knot L in a contact manifold M as the minimal genus of a page of an open book of M supporting the contact structure such that L sits on a page and the framing given by the contact structure and by the page agree. In this talk, we will discuss the support genus of Legendrian knots in contact 3-manifolds. We will show any null-homologous loose knot has support genus zero. To prove this, we observe an interesting topological property of knots and links on the way. We observe any topological knot or link in a 3-manifold sits on a planar page (genus zero page) of an open book decomposition.

Coupling with respect to initial conditions for deterministic dynamics

Series
Probability Working Seminar
Time
Friday, March 6, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 268
Speaker
Alex GrigoSchool of Mathematics, Georgia Tech
The talk is based on the paper titled "Anosov diffeomorphisms and coupling" by Bressaud and Liverani. Existence and uniqueness of SRB invariant measure for the dynamics is established via a coupling of initial conditions introduced to dynamics by L.-S. Young.

Graph parallel rigidity

Series
Combinatorics Seminar
Time
Friday, March 6, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Alexey SpiridonovMIT
This is joint work with Alex Postnikov. Imagine that you are to build a system of space stations (graph vertices), which communicate via laser beams (edges). The edge directions were already chosen, but you must place the stations so that none of the beams miss their targets. In this talk, we let the edge directions be generic and independent, a choice that constrains vertex placement the most. For K_{3} in \mathbb{R}^{2}, the edges specify a unique triangle, but its size is arbitrary --- D_{2}(K_{3})=1 degree of freedom; we say that K_{3} is rigid in \mathbb{R}^{2}. We call D_{n}(G) the degree of parallel rigidity of the graph for generic edge directions. We found an elegant combinatorial characterization of D_{n}(G) --- it is equal to the minimal number of edges in the intersection of n spanning trees of G. In this talk, I will give a linear-algebraic proof of this result, and of some other properties of D_{n}(G). The notion of parallel graph rigidity was previously studied by Whiteley and Develin-Martin-Reiner. The papers worked with the generic parallel rigidity matroid; I will briefly compare our results in terms of D_{n}(G) with the previous work.

Pages