- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

We show variants of spectral sparsification routines can preserve thetotal spanning tree counts of graphs, which by Kirchhoff's matrix-treetheorem, is equivalent to determinant of a graph Laplacian minor, orequivalently, of any SDDM matrix. Our analyses utilizes thiscombinatorial connection to bridge between statistical leverage scores/ effective resistances and the analysis of random graphs by [Janson,Combinatorics, Probability and Computing `94]. This leads to a routinethat in quadratic time, sparsifies a graph down to about $n^{1.5}$edges in ways that preserve both the determinant and the distributionof spanning trees (provided the sparsified graph is viewed as a randomobject). Extending this algorithm to work with Schur complements andapproximate Choleksy factorizations leads to algorithms for countingand sampling spanning trees which are nearly optimal for dense graphs.We give an algorithm that computes a $(1\pm \delta)$ approximation tothe determinant of any SDDM matrix with constant probability in about$n^2\delta^{−2}$ time. This is the first routine for graphs thatoutperforms general-purpose routines for computing determinants ofarbitrary matrices. We also give an algorithm that generates in about$n^2\delta^{−2}$ time a spanning tree of a weighted undirected graphfrom a distribution with total variation distance of $\delta$ fromthe w-uniform distribution.This is joint work with John Peebles, Richard Peng and Anup B. Rao.

Friday, October 13, 2017 - 10:00 ,
Location: Skiles 114 ,
Libby Taylor ,
GA Tech ,
Organizer: Timothy Duff

We will give an overview of divisor theory on curves and give
definitions of the Picard group and the Jacobian of a compact Riemann
surface. We will use these notions to prove Plucker’s formula for the
genus of a smooth projective curve. In addition,
we will discuss the various ways of defining the Jacobian of a curve and
why these definitions are equivalent. We will also give an extension
of these notions to schemes, in which we define the Picard group of a
scheme in terms of the group of invertible sheaves
and in terms of sheaf cohomology.

Series: Analysis Seminar

Dynamical sampling is the problem of recovering an
unknown function from a set of space-time samples. This problem has many
connections to problems in frame theory, operator theory and functional
analysis. In this talk, we will state the problem and discuss its
relations to various areas of functional analysis and operator theory,
and we will give a brief review of previous results and present several
new ones.

Wednesday, October 11, 2017 - 13:55 ,
Location: Skiles 006 ,
Justin Lanier ,
Georgia Tech ,
Organizer: Jennifer Hom

We will discuss the mapping class groupoid, how it is generated by handle slides, and how factoring in the mapping class groupoid can be used to compute Heegaard Floer homology. This talk is based on work by Lipshitz, Ozsvath, and Thurston.

Series: Other Talks

Lunch will be provided. The talk will be the first 25 minutes of the hour and then will be followed by discussion.

In a recent article to appear in the American Mathematical Mothly next year, we use the Lambert series generating function for Euler’s totient function to introduce a new identity for the number of 1’s in the partitions of n. New expansions for Euler’s partition function p(n) are derived in this context. These surprising new results connect the famous classical totient function from multiplicative number theory to the additive theory of partitions. We will define partitions and several variants of Euler's partition function in the talk to state our new results.

Series: Geometry Topology Seminar

Series: Combinatorics Seminar

Given a (fixed) graph H, let X be the number of copies of H in the random binomial graph G(n,p). In this talk we recall the results on the asymptotic behaviour of X, as the number n of vertices grows and pis allowed to depend on. In particular we will focus on the problem of estimating probability that X is significantly larger than its expectation, which earned the name of the 'infamous upper tail'.

Friday, October 6, 2017 - 15:00 ,
Location: Skiles 154 ,
Prof. Rafael de la Llave ,
School of Mathematics, Georgia Tech ,
Organizer: Jiaqi Yang

We will present an introduction to the results of S. Aubry and J. Mather who used variational methods to prove the existence of quasi-periodic orbits in twist mappings and in some models appearing in solid state Physics.

Friday, October 6, 2017 - 15:00 ,
Location: Skiles 154 ,
Sergio Mayorga ,
Georgia Tech ,
Organizer: Jiaqi Yang

We will look at a system of hamiltonian equations on the torus, with an
initial condition in momentum and a terminal condition in position, that
arises in mean field game theory. Existence of and uniqueness of
solutions will be shown, and a few remarks will be made in regard to its
connection to the minimization problem of a cost functional. This is the second part of lasrt week's talk.

Series: ACO Student Seminar

In a self-organizing particle system, an abstraction of programmable
matter, simple computational elements called particles with limited
memory and communication self-organize to solve system-wide problems of
movement, coordination, and configuration.
In this paper, we consider stochastic, distributed, local, asynchronous
algorithms for 'shortcut bridging', in which particles self-assemble
bridges over gaps that simultaneously balance minimizing the length and
cost of the bridge. Army ants of the genus Eticon
have been observed exhibiting a similar behavior in their foraging
trails, dynamically adjusting their bridges to satisfy an efficiency
tradeoff using local interactions. Using techniques from Markov chain
analysis, we rigorously analyze our algorithm, show
it achieves a near-optimal balance between the competing factors of path
length and bridge cost, and prove that it exhibits a dependence on the
angle of the gap being 'shortcut' similar to that of the ant bridges. We
also present simulation results that qualitatively
compare our algorithm with the army ant bridging behavior. Our work
presents a plausible explanation of how convergence to globally optimal
configurations can be achieved via local interactions by simple
organisms (e.g., ants) with some limited computational
power and access to random bits. The proposed algorithm demonstrates the
robustness of the stochastic approach to algorithms for programmable
matter, as it is a surprisingly simple extension of a stochastic
algorithm for compression.
This is joint work between myself/my professor Andrea Richa at ASU and Sarah Cannon and Prof. Dana Randall here at GaTech.