Seminars and Colloquia by Series

Approximate Clustering without the Approximation

Series
Combinatorics Seminar
Time
Friday, October 16, 2009 - 15:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Nina BalcanComputing Science & Systems, Georgia Tech
There has been substantial work on approximation algorithms for clustering data under distance-based objective functions such as k-median, k-means, and min-sum objectives. This work is fueled in part by the hope that approximating these objectives well will indeed yield more accurate solutions. That is, for problems such as clustering proteins by function, or clustering images by subject, there is some unknown correct "target" clustering and the implicit assumption is that clusterings that are approximately optimal in terms of these distance-based measures are also approximately correct in terms of error with respect to the target. In this work we show that if we make this implicit assumption explicit -- that is, if we assume that any c-approximation to the given clustering objective Phi is epsilon-close to the target -- then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, for the k-median, k-means, and min-sum objectives, we show that we can achieve this guarantee for any constant c > 1. Our results show how by explicitly considering the alignment between the objective function used and the true underlying clustering goals, one can bypass computational barriers and perform as if these objectives were computationally substantially easier. This talk is based on joint work with Avrim Blum and Anupam Gupta (SODA 2009), Mark Braverman (COLT 2009), and Heiko Roeglin and Shang-Hua Teng (ALT 2009).

Introduction to Heegaard Floer Homology

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

Please Note: This is a 2-hour talk.

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.

Shuffling biological sequences

Series
SIAM Student Seminar
Time
Friday, October 16, 2009 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Tianjun YeGeorgia Tech
This talk considers the following sequence shufling problem: Given a biological sequence (either DNA or protein) s, generate a random instance among all the permutations of s that exhibit the same frequencies of k-lets (e.g. dinucleotides, doublets of amino acids, triplets, etc.). Since certain biases in the usage of k-lets are fundamental to biological sequences, effective generation of such sequences is essential for the evaluation of the results of many sequence analysis tools. This talk introduces two sequence shuffling algorithms: A simple swapping-based algorithm is shown to generate a near-random instance and appears to work well, although its efficiency is unproven; a generation algorithm based on Euler tours is proven to produce a precisely uniforminstance, and hence solve the sequence shuffling problem, in time not much more than linear in the sequence length.

Point Perturbation and Asymptotics Orthogonal Polynomials

Series
Analysis Seminar
Time
Thursday, October 15, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 255 **NOTE ROOM CHANGE AND SPECIAL DAY**
Speaker
Lillian WongUniversity of Oklahoma
In this talk, I will discuss some results obtained in my Ph.D. thesis. First, the point mass formula will be introduced. Using the formula, we shall see how the asymptotics of orthogonal polynomials relate to the perturbed Verblunsky coefficients. Then I will discuss two classes of measures on the unit circle -- one with Verblunsky coefficients \alpha_n --> 0 and the other one with \alpha_n --> L (non-zero) -- and explain the methods I used to tackle the point mass problem involving these measures. Finally, I will discuss the point mass problem on the real line. For a long time it was believed that point mass perturbation will generate exponentially small perturbation on the recursion coefficients. I will demonstrate that indeed there is a large class of measures such that that proposition is false.

Positive Matrices and Applications to Hankel Operators

Series
Analysis Seminar
Time
Wednesday, October 14, 2009 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Marcus CarlssonPurdue University
Given an "infinite symmetric matrix" W we give a simple condition, related to the shift operator being expansive on a certain sequence space, under which W is positive. We apply this result to AAK-type theorems for generalized Hankel operators, providing new insights related to previous work by S. Treil and A. Volberg. We also discuss applications and open problems.

Cech cohomology of a sheaf

Series
Other Talks
Time
Wednesday, October 14, 2009 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
John EtnyreGa Tech
We will briefly review the definition of the Cech cohomology groups of a sheaf (so if you missed last weeks talk, you should still be able to follow this weeks), discuss some basic properties of the Cech construction and give some computations that shows how the theory connects to other things (like ordinary cohomology and line bundles).

[Special day and location] Scaling properties and suppression of Fermi acceleration in time dependent billiards

Series
Applied and Computational Mathematics Seminar
Time
Wednesday, October 14, 2009 - 13:00 for 8 hours (full day)
Location
Skiles 269
Speaker
Edson Denis LeonelUniversidade Estadual Paulista, Rio Claro, Brazil
Fermi acceleration is a phenomenon where a classical particle canacquires unlimited energy upon collisions with a heavy moving wall. Inthis talk, I will make a short review for the one-dimensional Fermiaccelerator models and discuss some scaling properties for them. Inparticular, when inelastic collisions of the particle with the boundaryare taken into account, suppression of Fermi acceleration is observed.I will give an example of a two dimensional time-dependent billiardwhere such a suppression also happens.

Introduction of variational approaches to image segmentation.

Series
Research Horizons Seminar
Time
Wednesday, October 14, 2009 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 171
Speaker
Sung Ha KangSchool of Mathematics, Georgia Tech
Image segmentation has been widely studied, specially since Mumford-Shah functional was been proposed. Many theoretical works as well as numerous extensions have been studied rough out the years. This talk will focus on introduction to these image segmentation functionals. I will start with the review of Mumford-Shah functional and discuss Chan-Vese model. Some new extensions will be presented at the end.

The neutral community model with random fission speciation

Series
Mathematical Biology Seminar
Time
Wednesday, October 14, 2009 - 11:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Bart HaegemanINRIA, Montpellier, France
Hubbell's neutral model provides a rich theoretical framework to study ecological communities. By coupling ecological and evolutionary time scales, it allows investigating how communities are shaped by speciation processes. The speciation model in the basic neutral model is particularly simple, describing speciation as a point mutation event in a birth of a single individual. The stationary species abundance distribution of the basic model, which can be solved exactly, fits empirical data of distributions of species abundances surprisingly well. More realistic speciation models have been proposed such as the random fission model in which new species appear by splitting up existing species. However, no analytical solution is available for these models, impeding quantitative comparison with data. Here we present a self-consistent approximation method for the neutral community model with random fission speciation. We derive explicit formulas for the stationary species abundance distribution, which agree very well with simulations. However, fitting the model to tropical tree data sets, we find that it performs worse than the original neutral model with point mutation speciation.

Boundary layer associated with the Darcy-Brinkman-Boussinesq system

Series
PDE Seminar
Time
Tuesday, October 13, 2009 - 15:05 for 1.5 hours (actually 80 minutes)
Location
Skiles 255
Speaker
Xiaoming WangFlorida State University
We study the asymptotic behavior of the infinite Darcy-Prandtl number Darcy-Brinkman-Boussinesq model for convection in porous media at small Brinkman-Darcy number. This is a singular limit involving a boundary layer with thickness proportional to the square root of the Brinkman-Darcynumber . This is a joint work with Jim Kelliher and Roger Temam.

Pages