- 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.

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.

Series: ACO Student Seminar

In 1995 Kim famously proved the Ramsey bound $R(3,t) \ge c t^2/\log t$ by constructing an $n$-vertex graph that is triangle-free and has independence number at most $C \sqrt{n \log n}$. We extend this celebrated result, which is best possible up to the value of the constants, by approximately decomposing the complete graph $K_n$ into a packing of such nearly optimal Ramsey $R(3,t)$ graphs. More precisely, for any $\epsilon>0$ we find an edge-disjoint collection $(G_i)_i$ of $n$-vertex graphs $G_i \subseteq K_n$ such that (a) each $G_i$ is triangle-free and has independence number at most $C_\epsilon \sqrt{n \log n}$, and (b) the union of all the $G_i$ contains at least $(1-\epsilon)\binom{n}{2}$ edges. Our algorithmic proof proceeds by sequentially choosing the graphs $G_i$ via a semi-random (i.e., Rödl nibble type) variation of the triangle-free process. As an application, we prove a conjecture in Ramsey theory by Fox, Grinshpun, Liebenau, Person, and Szabó (concerning a Ramsey-type parameter introduced by Burr, Erdös, Lovász in 1976). Namely, denoting by $s_r(H)$ the smallest minimum degree of $r$-Ramsey minimal graphs for $H$, we close the existing logarithmic gap for $H=K_3$ and establish that $s_r(K_3) = \Theta(r^2 \log r)$. Based on joint work with Lutz Warnke.

Series: ACO Student Seminar

In this talk, we study solvers for geometrically embedded graph structured block linear systems. The general form of such systems, PSD-Graph-Structured Block Matrices (PGSBM), arise in scientific computing, linear elasticity, the inner loop of interior point algorithms for linear programming, and can be viewed as extensions of graph Laplacians into multiple labels at each graph vertex. Linear elasticity problems, more commonly referred to as trusses, describe forces on a geometrically embedded object.We present an asymptotically faster algorithm for solving linear systems in well-shaped 3-D trusses. Our algorithm utilizes the geometric structures to combine nested dissection and support theory, which are both well studied techniques for solving linear systems. We decompose a well-shaped 3-D truss into balanced regions with small boundaries, run Gaussian elimination to eliminate the interior vertices, and then solve the remaining linear system by preconditioning with the boundaries.On the other hand, we prove that the geometric structures are ``necessary`` for designing fast solvers. Specifically, solving linear systems in general trusses is as hard as solving general linear systems over the real. Furthermore, we give some other PGSBM linear systems for which fast solvers imply fast solvers for general linear systems.Based on the joint works with Robert Schwieterman and Rasmus Kyng.

Series: ACO Student Seminar

The random to random shuffle on a deck of cards is given by at each
step choosing a random card from the deck, removing it, and replacing it
in a random location. We show an upper bound for the total variation
mixing time of the walk of 3/4n log(n) +cn steps. Together with matching
lower bound of Subag (2013), this shows the walk mixes with cutoff at
3/4n log(n) steps, answering a conjecture of Diaconis. We use the
diagonalization of the walk by Dieker and Saliola (2015), which relates
the eigenvalues to Young tableaux.
Joint work with Evita Nestorid.

Series: ACO Student Seminar

Beginning with Szemerédi’s regularity lemma, the theory of graph
decomposition and graph limits has greatly increased our understanding
of large dense graphs and provided a framework for graph approximation.
Unfortunately, much of this work does not meaningfully extend to
non-dense graphs. We present preliminary work towards our goal of
creating tools for approximating graphs of intermediate degree (average
degree o(n) and not bounded). We give a new random graph model that
produces a graph of desired size and density that approximates the
number of small closed walks of a given sparse graph (i.e., small
moments of its eigenspectrum). We show how our model can be applied to
approximate the hypercube graph. This is joint work with Santosh
Vempala.

Series: ACO Student Seminar

The concentration of measure phenomenon is of great importance in probabilistic combinatorics and theoretical computer science. For example, in the theory of random graphs, we are often interested in showing that certain random variables are concentrated around their expected values. In this talk we consider a variation of this theme, where we are interested in proving that certain random variables remain concentrated around their expected trajectories as an underlying random process (or random algorithm) evolves. In particular, we shall give a gentle introduction to the differential equation method popularized by Wormald, which allows for proving such dynamic concentration results. This method systematically relates the evolution of a given random process with an associated system of differential equations, and the basic idea is that the solution of the differential equations can be used to approximate the dynamics of the random process. If time permits, we shall also sketch a new simple proof of Wormalds method.

Series: ACO Student Seminar

We study stable marriage where individuals strategically submit private preference information to a publicly known stable marriage algorithm. We prove that no stable marriage algorithm ensures actual stability at every Nash equilibrium when individuals are strategic. More specifically, we show that any rational marriage, stable or otherwise, can be obtained at a Nash equilibrium. Thus the set of Nash equilibria provides no predictive value nor guidance for mechanism design. We propose the following new minimal dishonesty equilibrium refinement, supported by experimental economics results: an individual will not strategically submit preference list L if there exists a more honest L' that yields as preferred an outcome. Then for all marriage algorithms satisfying monotonicity and IIA, every minimally dishonest equilibrium yields a sincerely stable marriage. This result supports the use of algorithms less biased than the (Gale-Shapley) man-optimal, which we prove yields the woman-optimal marriage in every minimally dishonest equilibrium. However, bias cannot be totally eliminated, in the sense that no monotonic IIA stable marriage algorithm is certain to yield the egalitarian-optimal marriage in a minimally dishonest equilibrium – thus answering a 28-year old open question of Gusfield and Irving's in the negative. Finally, we show that these results extend to student placement problems, where women are polygamous and honest, but not to admissions problems, where women are both polygamous and strategic.
Based on joint work with Craig Tovey at Georgia Tech.

Series: ACO Student Seminar

Series: ACO Student Seminar

Using some classical results of invariant theory of finite reflection groups, and Lagrange multipliers, we prove that low degree or sparse real homogeneous polynomials
which are invariant under the action of a finite reflection group
$G$ are nonnegative if they are nonnegative on the hyperplane arrangement
$H$ associated to $G$. That makes $H$ a test set for the above kind of
polynomials. We also prove that under stronger sparsity conditions, for
the symmetric group and other reflection groups, the test set can
be much smaller. One of the main questions is deciding if certain
intersections of some simply constructed real $G$-invariant varieties are
empty or not.