Seminars and Colloquia by Series

Analyzing the R-MAT graph generator using occupancy theory

Series
Combinatorics Seminar
Time
Friday, January 29, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Blair Dowling SullivanOak Ridge National Labs
One of the biggest hurdles in high performance computing today is the analysis of massive quantities of data. As the size of the datasets grows to petascale (and beyond), new techniques are needed to efficiently compute meaningful information from the raw data. Graph-based data (which is ubiquitous in social networks, biological interaction networks, etc) poses additional challenges due to the difficulty of parallelizing many common graph algorithms. A key component in success is the generation of "realistic" random data sets for testing and benchmarking new algorithms. The R-MAT graph generator introduced by Chakrabarti, Faloutsos, and Zhan (2004) offers a simple, fast method for generating very large directed graphs. One commonly held belief regarding graphs produced by R-MAT is that they are "scale free"; in other words, their degree distribution follows a power law as is observed in many real world networks. These properties have made R-MAT a popular choice for generating graphs for use in a variety of research disciplines including graph theoretic benchmarks, social network analysis, computational biology, and network monitoring. However, despite its wide usage and elegant, parsimonius design, our recent work provides the first rigorous mathematical analysis of the degree distributions of the generated graphs. Applying results from occupancy problems in probability theory, we derive exact expressions for the degree distributions and other parameters. We also prove that in the limit (as the number of vertices tends to infinity), graphs generated with R-MAT have degree distributions that can be expressed as a mixture of normal distributions. This talk will focus on the techniques used in solving this applied problem in terms of classical "ball and urn" results, including a minor extension of Chistyakov's theorem.

Regularity and Geometry of Real Algebraic Convex Hypersurfaces

Series
Geometry Topology Working Seminar
Time
Friday, January 29, 2010 - 14:00 for 1.5 hours (actually 80 minutes)
Location
Skiles 269
Speaker
Mohammad Ghomi School of Mathematics, Georgia Tech
We prove that convex hypersurfaces M in R^n which are level sets of functions f: R^n --> R are C^1-regular if f has a nonzero partial derivative of some order at each point of M. Furthermore, applying this result, we show that if f is algebraic and M is homeomorphic to R^(n-1), then M is an entire graph, i.e., there exists a line L in R^n such that M intersects every line parallel L at precisely one point. Finally we will give a number of examples to show that these results are sharp.

The limit distribution the longest significance path(LSP) in point cloud

Series
SIAM Student Seminar
Time
Friday, January 29, 2010 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Kai NiSchool of Mathematics, Georgia Tech
In 2006, my coadvisor Xiaoming Huo and his colleague published an annal of statistics paper which designs an asymptotically powerful testing algorithm to detect the potential curvilinear structure in a messy point cloud image. However, such an algorithm involves a membership threshold and a decision threshold which are not well defined in that paper because the distribution of LSP was unknown. Later on, Xiaoming's student Chen, Jihong found some connections between the distribution of LSP and the so-called Erdos-Renyi law. In some sense, the distribution of LSP is just a generalization of the Erdos-Renyi law. However this JASA paper of Chen, Jihong had some restrictions and only partially found out the distribution of LSP. In this talk, I will show the result of the JASA paper is actually very close to the distribution of LSP. However, these is still much potential work to do in order to strengthen this algorithm.

Tropical geometry and applications

Series
Job Candidate Talk
Time
Thursday, January 28, 2010 - 16:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Josephine YuGeorgia Tech
Tropical geometry can be thought of as geometry over the tropical semiring, which is the set of real numbers together with the operations max and +. Just as ordinary linear and polynomial algebra give rise to convex geometry and algebraic geometry, tropical linear and polynomial algebra give rise to tropical convex geometry and tropical algebraic geometry. I will introduce the basic objects and problems in tropical geometry and discuss some relations with, and applications to, polyhedral geometry, computational algebra, and algebraic geometry.

Spin Glasses and other Combinatorial Optimization Problems

Series
Stochastics Seminar
Time
Thursday, January 28, 2010 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Stefan BoettcherEmory Physics
Finding ground states of spin glasses, a model of disordered materials, has a deep connection to many hard combinatorial optimization problems, such as satisfiability, maxcut, graph-bipartitioning, and coloring. Much insight has been gained for the combinatorial problems from the intuitive approaches developed in physics (such as replica theory and the cavity method), some of which have been proven rigorously recently. I present a treasure trove of numerical data obtained with heuristic methods that suggest a number conjectures, such as an equivalence between maxcut and bipartitioning for r-regular graphs, a simple relation for their optimal configurations as a function of degree r, and anomalous extreme-value fluctuations in a variety of models, hotly debated in physics currently. For some, such as those related to finite-size effects, not even a physics theory exists, for others theory exists that calls for rigorous methods.

On the independence of complex exponentials

Series
Analysis Seminar
Time
Thursday, January 28, 2010 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Mishko MitkovskiTexas A&M
Given a set of complex exponential e^{i \lambda_n x} how large do you have to take r so that the sequence is independent in L^2[-r,r] ? The answer is given in terms of the Beurling-Mallivan density.

The Geometric Weil Representation

Series
Algebra Seminar
Time
Wednesday, January 27, 2010 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 269
Speaker
Shamgar GurevichInstitute for Advanced Study, Princeton
This is a sequel to my first talk on "group representation patterns in digital signal processing". It will be slightly more specialized. The finite Weil representation is the algebra object that governs the symmetries of Fourier analysis of the Hilbert space L^2(F_q). The main objective of my talk is to introduce the geometric Weil representation---developed in a joint work with Ronny Hadani---which is an algebra-geometric (l-adic perverse Weil sheaf) counterpart of the finite Weil representation. Then, I will explain how the geometric Weil representation is used to prove the main results stated in my first talk. In the course, I will explain the Grothendieck geometrization procedure by which sets are replaced by algebraic varieties and functions by sheaf theoretic objects.

Using global invariant manifolds to understand metastability in Burgers equation with small viscosity

Series
PDE Seminar
Time
Tuesday, January 26, 2010 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
Margaret BeckBoston University
The large-time behavior of solutions to Burgers equation with small viscosity isdescribed using invariant manifolds. In particular, a geometric explanation is provided for aphenomenon known as metastability, which in the present context means that solutions spend avery long time near the family of solutions known as diffusive N-waves before finallyconverging to a stable self-similar diffusion wave. More precisely, it is shown that in termsof similarity, or scaling, variables in an algebraically weighted L^2 space, theself-similar diffusion waves correspond to a one-dimensional global center manifold ofstationary solutions. Through each of these fixed points there exists a one-dimensional,global, attractive, invariant manifold corresponding to the diffusive N-waves. Thus,metastability corresponds to a fast transient in which solutions approach this ``metastable"manifold of diffusive N-waves, followed by a slow decay along this manifold, and, finally,convergence to the self-similar diffusion wave. This is joint work with C. Eugene Wayne.

Variational problems involving area (continued)

Series
Research Horizons Seminar
Time
Tuesday, January 26, 2010 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 255
Speaker
John McCuanSchool of Math, Georgia Tech

Please Note: Hosted by: Huy Huynh and Yao Li

In the preceeding talk, I outlined a framework for variational problems and some of the basic tools and results. In this talk I will attempt describe several problems of current interest.

Pages