Seminars and Colloquia by Series

Maximizing expected utility over a knapsack constraint

Series
ACO Student Seminar
Time
Friday, September 28, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jiajin YuCollege of Computing, Georgia Tech
This work develops approximation algorithms for a stochastic knapsack problem involving an expected utility objective. The values of the items in the knapsack can only be sampled from an oracle, and the objective function is a concave function of the total value of the items in the knapsack. We will first show a polynomial number of samples is enough to approximate the true expected value close enough. Then we will present an algorithm that maximizes a class of submodular function under knapsack constraint with approximation ratio better than 1-1/e. We will also see better bounds when the concave function is a power function. At last, if time permits, we will give an FPTAS of the problem when the number of scenarios is fixed.

Stochastic Target Approach to Ricci Flow on surfaces

Series
Stochastics Seminar
Time
Thursday, September 27, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Ionel PopescuSchool of Mathematics, Georgia Tech
Ricci flow is a sort of (nonlinear) heat problem under which the metric on a given manifold is evolving. There is a deep connection between probability and heat equation. We try to setup a probabilistic approach in the framework of a stochastic target problem. A major result in the Ricci flow is that the normalized flow (the one in which the area is preserved) exists for all positive times and it converges to a metric of constant curvature. We reprove this convergence result in the case of surfaces of non-positive Euler characteristic using coupling ideas from probability. At certain point we need to estimate the second derivative of the Ricci flow and for that we introduce a coupling of three particles. This is joint work with Rob Neel.

Some coloring problems on random graphs

Series
Combinatorics Seminar
Time
Thursday, September 27, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Alan FriezeMath, Carnegie Mellon University
We will discuss some problems related to coloring the edges or vertices of a random graph. In particular we will discuss results on (i) the game chromatic number; (ii) existence of rainbow Hamilton cycles; (iii) rainbow connection. (** Please come a few minutes earlier for a pizza lunch **)

Genericity of chaotic behavior

Series
School of Mathematics Colloquium
Time
Thursday, September 27, 2012 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Yakov PesinPenn State
It is well-known that a deterministic dynamical system can exhibit stochastic behavior that is due to the fact that instability along typical trajectories of the system drives orbits apart, while compactness of the phase space forces them back together. The consequent unending dispersal and return of nearby trajectories is one of the hallmarks of chaos. The hyperbolic theory of dynamical systems provides a mathematical foundation for the paradigm that is widely known as "deterministic chaos" -- the appearance of irregular chaotic motions in purely deterministic dynamical systems. This phenomenon is considered as one of the most fundamental discoveries in the theory of dynamical systems in the second part of the last century. The hyperbolic behavior can be interpreted in various ways and the weakest one is associated with dynamical systems with non-zero Lyapunov exponents. I will discuss the still-open problem of whether dynamical systems with non-zero Lyapunov exponents are typical. I will outline some recent results in this direction. The genericity problem is closely related to two other important problems in dynamics on whether systems with nonzero Lyapunov exponents exist on any phase space and whether nonzero exponents can coexist with zero exponents in a robust way.

Ends of Nonpositively Curved Manifolds

Series
Research Horizons Seminar
Time
Wednesday, September 26, 2012 - 12:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Igor BelegradekGeorgia Tech, School of Math
In the talk we will start from examples of open surfaces, such as the complex plane minus a Cantor set, review their classification, and then move to higher dimensions, where we discuss ends of manifolds in the topological setting, and finally in the geometric setting under the assumption of nonpositive curvature.

On the extension of sharp Hardy-Littlewood-Sobolev inequality

Series
PDE Seminar
Time
Tuesday, September 25, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Meijun ZhuUniversity of Oklahoma
We shall describe our recent work on the extension of sharp Hardy-Littlewood-Sobolev inequality, including the reversed HLS inequality with negative exponents. The background and motivation will be given. The related integral curvature equations may be discussed if time permits.

Discrete Mathematical Biology Working Seminar

Series
Other Talks
Time
Tuesday, September 25, 2012 - 10:00 for 1 hour (actually 50 minutes)
Location
Skiles 114
Speaker
Will PerkinsGeorgia Tech
Further discussion of co-transcriptional RNA folding, and the potential for trap models to capture these dynamics.

Algorithms for symmetric Gröbner bases

Series
Algebra Seminar
Time
Monday, September 24, 2012 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Robert KroneGeorgia Tech
A symmetric ideal in the polynomial ring of a countable number of variables is an ideal that is invariant under any permutations of the variables. While such ideals are usually not finitely generated, Aschenbrenner and Hillar proved that such ideals are finitely generated if you are allowed to apply permutations to the generators, and in fact there is a notion of a Gröbner bases of these ideals. Brouwer and Draisma showed an algorithm for computing these Gröbner bases. Anton Leykin, Chris Hillar and I have implemented this algorithm in Macaulay2. Using these tools we are exploring the possible invariants of symmetric ideals that can be computed, and looking into possible applications of these algorithms, such as in graph theory.

Towards flexibility for higher-dimensional contact manifolds

Series
Geometry Topology Seminar
Time
Monday, September 24, 2012 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Olga PlamenevskayaSUNY - Stony Brook
By a classical result of Eliashberg, contact manifolds in dimension 3 come in two flavors: tight (rigid) and overtwisted (flexible). Characterized by the presence of an "overtwisted disk", the overtwisted contact structures form a class where isotopy and homotopy classifications are equivalent.In higher dimensions, a class of flexible contact structures is yet to be found. However, some attempts to generalize the notion of an overtwisted disk have been made. One such object is a "plastikstufe" introduced by Niederkruger following some ideas of Gromov. We show that under certain conditions, non-isotopic contact structures become isotopic after connect-summing with a contact sphere containing a plastikstufe. This is a small step towards finding flexibility in higher dimensions. (Joint with E. Murphy, K. Niederkruger, and A. Stipsicz.)

Pages