Seminars and Colloquia by Series

Graph Patches (Partial Sparsifiers) and their applications to designing cost-effective, expanding networks

Series
Combinatorics Seminar
Time
Friday, April 3, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Alexandra KollaUC Berkeley
I will present an approximation algorithm for the following problem: Given a graph G and a parameter k, find k edges to add to G as to maximize its algebraic connectivity. This problem is known to be NP-hard and prior to this work no algorithm was known with provable approximation guarantee. The algorithm uses a novel way of sparsifying (patching) part of a graph using few edges.

Small random perturbation of ODE around hyperbolic points

Series
SIAM Student Seminar
Time
Friday, April 3, 2009 - 12:30 for 2 hours
Location
Skiles 269
Speaker
Sergio AlmadaSchool of Mathematics, Georgia Tech
Suppose b is a vector field in R^n such that b(0) = 0. Let A = Jb(0) the Jacobian matrix of b at 0. Suppose that A has no zero eigenvalues, at least one positive and at least one negative eigenvalue. I will study the behavior of the stochastic differential equation dX_\epsilon = b(X_\epsilon) + \epsilon dW as \epsilon goes to 0. I will illustrate the techniques done to deal with this kind of equation and make remarks on how the solution behaves as compared to the deterministic case.

The power of LP and SDP hierarchies and integrality gaps through semidefinite programming duality

Series
ACO Student Seminar
Time
Thursday, April 2, 2009 - 13:30 for 2 hours
Location
Skiles 255
Speaker
Alexandra KollaUC Berkeley
In the first part of the talk, I am going to give an introduction and overview of linear and semidefinite programming hierarchies. I will mostly review known integrality gaps for such programs and try to give an intuition of why we currently lack strong techniques for designing rounding algorithms. In the second part of the talk I will focus on the stronger SDP Lasserre hierarchy. In contrast with the previous LP and SDP hierarchies, very few examples of integrality gap instances are known to date. I will present a recent technique for designing such instances and discuss open problems in the area.

Compensated compactness and isometric embedding

Series
School of Mathematics Colloquium
Time
Thursday, April 2, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Marshall SlemrodDepartment of Mathematics, University of Wisconsin
In this talk I will outline recent results of G-Q Chen, Dehua Wang, and me on the problem of isometric embedding a two dimensional Riemannian manifold with negative Gauss curvature into three dimensional Euclidean space. Remarkably there is very pretty duality between this problem and the equations of steady 2-D gas dynamics. Compensated compactness (L.Tartar and F.Murat) yields proof of existence of solutions to an initial value problem when the prescribed metric is the one associated with the catenoid.

The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD

Series
ACO Colloquium
Time
Wednesday, April 1, 2009 - 16:30 for 2 hours
Location
Klaus 1116E
Speaker
Ilan AdlerUC Berkeley
One of the most interesting aspects of the Linear Complementarity Problem (LCP) is its range from relatively easy problems such as linear and convex quadratic programming problems to NP-hard problems. A major effort in LCP theory had been the study of the Lemke algorithm, a simplex-like algorithm which is guaranteed to terminate in finite number of iterations but not necessarily with a solution (or a certificate that no solution exists). Over the years, many subclasses of LCP were proven to be workable by the Lemke algorithm. Those subclasses were often characterized as ‘nice’ even when no polynomial upper bound for the algorithm was known to exist. In fact, for most of these classes, instances with exponential number of steps had been discovered. In this talk, I’ll discuss the close connection between these classes and the PPAD (Polynomial-time Parity Argument Directed) complexity class. The discovery that computing Nash equilibrium (which is an LCP) is PPAD complete is particularly significant in analyzing the complexity of LCP. I’ll also discuss the LCP reduction-via-perturbation technique and its relation to the PPAD class and the Lemke Algorithm. This talk is based on a joint work with Sushil Verma.

Mathematical and experimental considerations of density and physiological state effects on antimicrobial susceptibility

Series
Mathematical Biology Seminar
Time
Wednesday, April 1, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Klas UdekwuEmory University
The treatment of bacterial infections with antibiotics is universally accepted as one of (if not THE) most significant contributions of medical intervention to reducing mortality and morbidity during last century. Despite their widespread use over this extended period however, basic knowledge about how antibiotics kill or prevent the growth of bacteria is only just beginning to emerge. The dose and term of antibiotic treatment has long been determined empirically and intuitively by clinicians. Only recently have antibiotic treatment protocols come under scrutiny with the aim to theoretically and experimentally rationalize treatment protocols. The aim of such scrutiny is to design protocols which maximize antibiotics’ efficacy in clearing bacterial infections and simultaneously prevent the emergence of resistance in treated patients. Central to these endeavors are the pharmacodynamics, PD (relationship between bug and drug), and the pharmacokinetics, PK (the change antibiotic concentration with time) of each bacteria : drug : host combination. The estimation of PD and PK parameters is well established and standardized worldwide and although different PK parameters are commonly employed for most of these considerations, a single PD parameter is usually used, the minimum inhibitory concentration (MIC). MICs, also utilized as the criteria for resistance are determined under conditions that are optimal to the action of the antibiotic; low densities of bacteria growing exponentially. The method for estimating MICs which is the only one officially sanctioned by the regulatory authority (Clinical and Laboratory Standards Institute) defines conditions that rarely obtain outside of the laboratory and virtually never in the bacteria infecting mammalian hosts. Real infections with clinical symptoms commonly involve very high densities of bacteria, most of which are not replicating. These populations are rarely planktonic but rather reside as colonies or within matrices called biofilms which sometimes include other species of bacteria. In the first part of my talk, I will present newly published data that describes the pharmacodynamic relationship between the sometimes pathogenic bacterium Staphylococcus aureus and antibiotics of six classes and the effects of cell density on MICs. By including density dependent MIC in a standard mathematical model of antibiotic treatment (from our lab), I show that this density-dependence may explain why antibiotic treatment fails in the absence of inherited resistance. In the second part of my talk I will consider the effects of the physiological state of clinical isolates of S. aureus on their susceptibility to different antibiotics. I present preliminary data which suggests that the duration of an infection may contribute adversely to an antibiotics chance of clearing the infection. I conclude with a brief discussion of the implications of the theoretical and experimental results for the development of antibiotic treatment protocols. As a special treat, I will outline problems of antibiotic treatment that could well be addressed with some classy mathematics.

Existence of Hyperbolic Systems with Prescribed Geometry

Series
PDE Seminar
Time
Tuesday, March 31, 2009 - 15:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Kris JenssenPenn State University, College Station
We study the problem of constructing systems of hyperbolic conservation laws with prescribed eigencurves, i.e. the eigenvector fields of the Jacobian of the flux are given. We formulate this as a (typically overdetermined) system of equations for the eigenvalues-to-be. Equivalent formulations in terms of differential and algebraic-differential equations are considered. The resulting equations are then analyzed with techniques from exterior differential systems (Cartan-Kahler theory). The cases of 2x2- and 3x3-systems can be treated in detail, and explicit examples show that already the 3x3-case is fairly complex. We also analyze general rich systems. We also characterize conservative systems with the same eigencurves as compressible gas dynamics. This is joint work with Irina Kogan (North Carolina State University).

On capacity allocation in queueing networks

Series
CDSNS Colloquium
Time
Monday, March 30, 2009 - 16:30 for 2 hours
Location
Skiles 255
Speaker
Ton DiekerISyE, Georgia Tech
Allocation of service capacity ('staffing') at stations in queueing networks is both of fundamental and practical interest. Unfortunately, the problem is mathematically intractable in general and one therefore typically resorts to approximations or computer simulation. This talk describes work in progress with M. Squillante and S. Ghosh (IBM Research) on an algorithm that serves as an approximation for the 'best' capacity allocation rule. The algorithm can be interpreted as a discrete-time dynamical system, and we are interested in uniqueness of a fixed point and in convergence properties. No prior knowledge on queueing networks will be assumed.

Contracted asymptotics for orthogonal polynomials with unbounded recurrence coefficients

Series
Analysis Seminar
Time
Monday, March 30, 2009 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Jeff GeronimoSchool of Mathematics, Georgia Tech
The contracted asymptotics for orthogonal polynomials whose recurrence coefficients tend to infinity will be discussed. The connection between the equilibrium measure for potential problems with external fields will be exhibited. Applications will be presented which include the Wilson polynomials.

Hyperbolic volume and the complexity of Heegaard splittings of 3-manifolds

Series
Geometry Topology Seminar
Time
Monday, March 30, 2009 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Yo'av Rieck University of Arkansas
Let M be a hyperbolic 3-manifold, that is, a 3-manifold admitting a complete, finite volume Riemannian metric of constant section curvature -1. Let S be a Heegaard surface in M, that is, M cut open along S consists of two handlebodies. Our goal is to prove that is the volume of M (denoted Vol(M)) if small than S is simple. To that end we define two complexities for Heegaard surfaces. The first is the genus of the surface (denoted g(S)) and the second is the distance of the surface, as defined by Hempel (denoted d(S)). We prove that there exists a constant K>0 so that for a generic manifold M, if g(S) \geq 76KVol(M) + 26, then d(S) \leq 2. Thus we see that for a generic manifold of small volume, either the genus of S is small or its distance is at most two. The term generic will be explained in the talk.

Pages