Seminars and Colloquia by Series

Tuesday, February 23, 2010 - 12:00 , Location: Skiles 255 , Prasad Tetali , Professor, School of Mathematics and School of Computer Science , Organizer:

Hosted by: Huy Huynh and Yao Li

Sampling from and approximately counting the size of a large set
of combinatorial structures has contributed to a renaissance in research
in finite Markov chains in the last two decades.
Applications are wide-ranging from sophisticated card shuffles,
deciphering simple substitution ciphers (of
prison inmates in the California state prison), estimating the volume of
a high-dimensional convex body,
and to understanding the speed of Gibbs sampling heuristics in
statistical physics. More recent applications include rigorous estimates
on J.M. Pollard's (1979) classical Rho and Kangaroo algorithms for the
discrete logarithm problem in finite cyclic groups.
The lecture will be a brief (mostly self-contained) introduction to the
Markov Chain Monte Carlo (MCMC) methodology and applications, and will
include some open problems.
Monday, February 22, 2010 - 13:00 , Location: Skiles 255 , Heasoon Park , CSE, Georgia Institute of Technology , Organizer: Sung Ha Kang
Nonnegative Matrix
Factorization (NMF) has attracted much attention during the past
decade as a dimension reduction method in machine learning and data
analysis. NMF provides a lower rank approximation of a nonnegative
high dimensional matrix by factors whose elements are also
nonnegative. Numerous success stories were reported in application
areas including text clustering, computer vision, and cancer class
discovery.

In
this talk, we present novel algorithms for NMF and NTF (nonnegative
tensor factorization) based on the alternating non-negativity
constrained least squares (ANLS) framework. Our new algorithm for NMF
is built upon the block principal pivoting method for the
non-negativity constrained least squares problem that overcomes some
limitations of the classical active set method. The proposed NMF
algorithm can naturally be extended to obtain highly efficient NTF
algorithm for PARAFAC (PARAllel FACtor) model. Our algorithms
inherit the convergence theory of the ANLS framework and can easily
be extended to other NMF formulations such as sparse NMF and NTF with
L1 norm constraints. Comparisons of algorithms using various data
sets show that the proposed new algorithms outperform existing ones
in computational speed as well as the solution quality.

This
is a joint work with Jingu Kim and Krishnakumar Balabusramanian.

Monday, February 22, 2010 - 13:00 , Location: Skiles 269 , Michael Lacey , Georgia Tech , Organizer: Michael Lacey
We will start a discussion of arXiv:1001.4043, which characterizes the two weight inequality for the Hilbert transform, including the statement of the theorem, and some examples of how this question arises. Joint work with Ignacio Uriate-Tuero, and Eric Sawyer.
Series: Other Talks
Saturday, February 20, 2010 - 09:00 , Location: Skiles 249 , Georgia Scientific Computing Symposium , School of Mathematics, Georgia Tech , Organizer: Sung Ha Kang
The purpose of the Georgia Scientific Computing Symposium (GSC 2010) is to provide an opportunity for professors, postdocs and graduate students in the Atlanta area to meet in an informal setting, to exchange ideas, and to highlight local scientific computing research. The one-day symposium is open to the whole research community. The event is free but registration is required.
Friday, February 19, 2010 - 15:00 , Location: Skiles 169 , Tobias Hurth , Georgia Tech , Organizer:
In my talk, I will present the main results of a recent article by Martin Hairer and Jonathan Mattingly on an ergodic theorem for Markov chains. I will consider Markov chains evolving in discrete time on an abstract, possibly uncountable, state space. Under certain regularity assumptions on the chain's transition kernel, such as the existence of a Foster-Lyapunov function with small level sets (what exactly is meant by that will be thoroughly explained in the talk), one can establish the existence and uniqueness of a stationary distribution. I will focus on a new proof technique for that theorem which relies on a family of metrics on the set of probability measures living on the state space. The main result of my talk will be a strict contraction estimate involving these metrics.
Friday, February 19, 2010 - 14:00 , Location: Skiles 269 , Anh Tran , Georgia Tech , Organizer:

This is part 1 of a two part talk. The second part will continue next week.

I will introduce the AJ conjecture (by Garoufalidis)
which relates the A-polynomial and the colored Jones polynomial of a
knot in the 3-sphere. Then I will verify it for the trefoil and the
figure 8 knots (due to Garoufalidis) and torus knots (due to Hikami) by
explicit calculations.
Friday, February 19, 2010 - 13:00 , Location: Skiles 255 , Craig A. Sloane , School of Mathematics, Georgia Tech , Organizer:
This will be an introductory talk about Hardy inequalities. These inequalities are solutions to optimization problems, and their results are well-known. I will survey these results, and discuss some of the techniques used to solve these problems. The applications of Hardy inequalities are broad, from PDE's and mathematical physics to brownian motion. This talk will also serve as a lead-in to my talk at the Analysis seminar next Wednesday in which I discuss some current results that Michael Loss and I have obtained.
Thursday, February 18, 2010 - 16:00 , Location: Skiles 269 , Raman Parimala , Department of Mathematics and Computer Science, Emory University , Organizer: Guillermo Goldsztein
Let k be a p-adic field and K/k function field in one variable
over k. We discuss Hasse principle for existence of rational points
on homogeneous spaces under connected linear algebraic groups.
We illustrate how a positive answer to Hasse principle leads for instance to the result:
every quadratic form in nine variables over K has a nontrivial zero.
Thursday, February 18, 2010 - 12:05 , Location: Skiles 255 , Professor Jason Gao , School of Mathematics and Statistics Carleton University , zgao@math.carleton.ca , Organizer: Xingxing Yu
A map is a connected graph G embedded in a surface S (a closed 2-manifold) such that all components of S -- G are simply connected regions. A map is rooted if an edge is distinguished together with a direction on the edge and a side of the edge. Maps have been enumerated by both mathematicians and physicists as they appear naturally in the study of representation theory, algebraic geometry, and quantum gravity. In 1986 Bender and Canfield showed that the number of n-edge rooted maps on an orientable surface of genus g is asymptotic to t_g n^{5(g-1)/2}12n^n, (n approaches infinity), where t_g is a positive constant depending only on g. Later it was shown that many families of maps satisfy similar asymptotic formulas in which tg appear as \universal constants". In 1993 Bender et al. derived an asymptotic formula for the num- ber of rooted maps on an orientable surface of genus g with i faces and j vertices. The formula involves a constant tg(r) (which plays the same role as tg), where r is determined by j=i.In this talk, we will review how these asymptotic formulas are obtained using Tutte's recursive approach. Connections with random trees, representation theory, integrable systems, Painleve I, and matrix integrals will also be mentioned. In particular, we will talk aboutour recent results about a simple relation between tg(r) and tg, and asymptotic formulas for the numbers of labeled graphs (of various connectivity)of a given genus. Similar results for non-orientable surfaces will also be discussed.
Wednesday, February 17, 2010 - 16:30 , Location: Skiles 255 (Refreshments at 4pm in Skiles 236) , David Gamarnik , Professor, M.I.T. , gamarnik@mit.edu , Organizer: Prasad Tetali
We establish the existence of scaling limits for several combinatorial optimization models on Erdos-Renyi and sparse random regular graphs. For a variety of models, including maximum independent sets, MAX-CUT, coloring and K-SAT, we prove that the optimal value appropriately rescaled, converges to a limit with high probability (w.h.p.), as the size of the underlying graph divergesto infinity. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. thus resolving an open problem. Our approach is based on developing a simple combinatorial approach to an interpolation method developed recently in the statistical physics literature. Among other things, theinterpolation method was used to prove the existence of the so-called free energy limits for several spin glass models including Viana-Bray and random K-SAT models. Our simpler combinatorial approach allows us to work with the zero temperature case (optimization) directly and extend the approach to many other models. Additionally, using our approach, we establish the large deviationsprinciple for the satisfiability property for constraint satisfaction problems such as coloring, K-SAT and NAE(Not-All-Equal)-K-SAT. The talk will be completely self-contained. No background on random graph theory/statistical physics is necessary. Joint work with Mohsen Bayati and Prasad Tetali

Pages