Seminars and Colloquia by Series

Series: ACO Seminar
Monday, March 23, 2009 - 16:30 , Location: Skiles 269 , Andrea Montanari , Stanford University , Organizer: Prasad Tetali
Low-rank models are frequently used in machine learning and statistics. An important domain of application is provided by collaborative filtering, whereby a low-rank matrix describes the ratings that a large set of users attribute to a large set of products. The problem is in this case to predict future ratings from a sparse subset currently available. The dataset released for the Netflix challenge provides an ideal testbed for theory and algorithms for learning low-rank matrices. Given M, a random n x n matrix of rank r, we assume that a uniformly random subset E of its entries is observed. We describe an efficient procedure that reconstructs M from |E| = O(rn) observed entries with arbitrarily small root mean square error, whenever M is satisfies an appropriate incoherence condition. If r = O(1), the algorithm reconstructs M exactly from O(n log n) entries. This settles a recent open problem by Candes and Recht. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices. [Based on joint work with R. H. Keshavan and S. Oh]
Monday, March 23, 2009 - 13:00 , Location: Skiles 255 , Shigui Ruan , University of Miami , Organizer: Yingfei Yi
Understanding the seasonal/periodic reoccurrence of influenza will be very helpful in designing successful vaccine programs and introducing public health interventions. However, the reasons for seasonal/periodic influenza epidemics are still not clear even though various explanations have been proposed. In this talk, we present an age-structured type evolutionary epidemiological model of influenza A drift, in which the susceptible class is continually replenished because the pathogen changes genetically and immunologically from one epidemic to the next, causing previously immune hosts to become susceptible. Applying our recent established center manifold theory for semilinear equations with non-dense domain, we show that Hopf bifurcation occurs in the model. This demonstrates that the age-structured type evolutionary epidemiological model of influenza A drift has an intrinsic tendency to oscillate due to the evolutionary and/or immunological changes of the influenza viruses. (based on joint work with Pierre Magal).
Thursday, March 19, 2009 - 11:00 , Location: Skiles 269 , Sergey Norin , Princeton University , Organizer: Robin Thomas
Many results in asymptotic extremal combinatorics are obtained using just a handful of instruments, such as induction and Cauchy-Schwarz inequality. The ingenuity lies in combining these tools in just the right way. Recently, Razborov developed a flag calculus which captures many of the available techniques in pure form, and allows one, in particular, to computerize the search for the right combination. In this talk we outline the general approach and describe its application to the conjecture that a digraph with minimum outdegree n/3 contains a directed triangle. This special case of the Caccetta-Haggkvist conjecture has been extensively investigated in the past. We show that a digraph with minimum outdegree a*n contains a directed triangle for a = 0.3465. The proof builds on arguments used to establish previously known bounds, due to Shen from 1998 (a = 0.3542) and Hamburger, Haxell and Kostochka from 2008 (a = 0.3531). It consists of a combination of ~80 computer generated inequalities. Based on joint work with Jan Hladky and Daniel Kral.
Series: PDE Seminar
Friday, March 13, 2009 - 16:05 , Location: Skiles 255 , Eitan Tadmor , University of Maryland, College Park , Organizer:
We discuss the global regularity vs. finite time breakdown in Eulerian dynamics, driven by different models of nonlinear forcing. Finite time breakdown depends on whether the initial configuration crosses intrinsic, O(1) critical thresholds (CT). Our approach is based on spectral dynamics, tracing the eigenvalues of the velocity gradient which determine the boundaries of CT surfaces in configuration space. We demonstrate this critical threshold phenomena with several n-dimensional prototype models. For n=2 we show that when rotational forcing dominates the pressure, it prolongs the life-span of sub-critical 2D shallow-water solutions. We present a stability theory for vanishing viscosity solutions of the 2D nonlinear "pressureless" convection. We revisit the 3D restricted Euler and Euler-Poisson equations, and obtain a surprising global existence result for a large set of sub-critical initial data in the 4D case.
Friday, March 13, 2009 - 14:00 , Location: Skiles 255 , George Sell , University of Minnesota , Organizer: Yingfei Yi
The current theory of global attractors for the Navier-Stokes equations on thin 3D domains is motivated by the desire to better understand the theory of heat transfer in the oceans of the Earth. (In this context, the thinness refers to the aspect ratio - depth divided by expanse - of the oceans.) The issue of heat transfer is, of course, closely connected with many of the major questions concerning the climate. In order to exploit the tools of modern dynamical systems in this study, one needs to know that the global attractors are "good" in the sense that the nonlinearities are Frechet differentiable on these attractors. About 20 years ago, it was discovered that on certain thin 3D domains, the Navier-Stokes equations did possess good global attractors. This discovery, which was itself a major milestone in the study of the 3D Navier-Stokes equations, left open the matter of extending the theory to cover oceanic-like regions with the appropriate physical boundary behavior. In this lecture, we will review this theory, and the connections with climate modeling, while placing special emphasis on the recent developments for fluid flows with the Navier (or slip) boundary conditions
Thursday, March 12, 2009 - 15:00 , Location: Skiles 269 , Hayrie Ayhan , ISyE, Georgia Tech , Organizer: Heinrich Matzinger
We consider Markovian tandem queues with finite intermediate buffers and flexible servers and study how the servers should be assigned dynamically to stations in order to obtain optimal long-run average throughput. We assume that each server can work on only one job at a time, that several servers can work together on a single job, and that the travel times between stations are negligible. Under various server collaboration schemes, we characterize the optimal server assignment policy for these systems.
Thursday, March 12, 2009 - 11:05 , Location: Skiles 269 , Ian F. Putnam , U. Victoria, BC, Canada , Organizer: Jean Bellissard
Motivated by Smale's work on smooth dynamical systems, David Ruelle introduced the notion of Smale spaces. These are topological dynamical systems which are hyperbolic in the sense of having local coordinates of contracting and expending directions. These include hyperbolic automorphisms of tori, but typically, the spaces involved have a fractal nature. An important subclass are the shifts of finite type which are symbolic systems described by combinatorial data. These are also precisely the Smale spaces which are totally disconnected. Rufus Bowen showed that every Smale space is the image of shift of finite type under a finite-to-one factor map. In the 1970's, Wolfgang Krieger introduced a beautiful invariant for shifts of finite type. The aim of this talk is to show how a refined version of Bowen's theorem may be used to extend Krieger's invariant to all (irreducible) Smale spaces. The talk will assume no prior knowledge of these topics - we begin with a discussion of Smale spaces and shifts of finite type and then move on to Krieger's invariant and its extension.
Series: ACO Seminar
Wednesday, March 11, 2009 - 16:00 , Location: Klaus 2100 , Nikhil Devanur , Microsoft Research , Organizer: Robin Thomas
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.
Wednesday, March 11, 2009 - 12:00 , Location: Skiles 255 , Hao Min Zhou , School of Mathematics, Georgia Tech , Organizer:
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.
Wednesday, March 11, 2009 - 11:00 , Location: Skiles 269 , Ann Trenk , Department of Mathematics, Wellesley College , Organizer: Prasad Tetali
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.

Pages