Fall 2017, Spring 2018

Subscribe to the ACO Student Seminar mailing list.

Algorithm and Hardness for Linear Elasticity Problems

**Abstract:** 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.

Packing nearly optimal Ramsey R(3,t) Graphs

**Abstract:**
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.

A Stochastic Approach to Shortcut Bridging in Programmable Matter

**Abstract: **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.

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

**Abstract:**
We show variants of spectral sparsification routines can preserve the
total spanning tree counts of graphs, which by Kirchhoff's matrix-tree
theorem, is equivalent to determinant of a graph Laplacian minor, or
equivalently, of any SDDM matrix. Our analyses utilizes this
combinatorial 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 routine
that in quadratic time, sparsifies a graph down to about \(n^{1.5}\)
edges in ways that preserve both the determinant and the distribution
of spanning trees (provided the sparsified graph is viewed as a random
object). Extending this algorithm to work with Schur complements and
approximate Choleksy factorizations leads to algorithms for counting
and sampling spanning trees which are nearly optimal for dense graphs.

We give an algorithm that computes a \((1\pm \delta)\) approximation to
the determinant of any SDDM matrix with constant probability in about
\(n^2\delta^{−2}\) time. This is the first routine for graphs that
outperforms general-purpose routines for computing determinants of
arbitrary matrices. We also give an algorithm that generates in about
\(n^2\delta^{−2}\) time a spanning tree of a weighted undirected graph
from a distribution with total variation distance of \(\delta\) from
the w-uniform distribution.

This is joint work with John Peebles, Richard Peng and Anup B. Rao.

The list chromatic number of graphs with small clique number

**Abstract:** We prove that every triangle-free graph with maximum
degree \(\Delta\) has list chromatic number at most \((1+o(1))\frac{\Delta}{\ln
\Delta}\). This matches the best-known bound for graphs of girth at least
5. We also provide a new proof that for any \(r\geq4\) every
\(K_r\)-free graph has list-chromatic number at most
\(200r\frac{\Delta\ln\ln\Delta}{\ln\Delta}\).

86 Years of Ramsey R(3,k). (and counting!)

**Abstract:** The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe, America, Korea and Rio de Janiero. We explore it through a CS lens, giving algorithms that provide the various upper and lower bounds. The arguments are various more or less sophisticated uses of Erdos Magic and, indeed, many of the most important advances in the Probabilistic Method have come from these investigations.