ACO Student Seminar
Fall 2017, Spring 2018


Description

The Georgia Tech ACO Student Seminar is run by students in the ACO program. The propose of this seminar is to keep students updated with current researches, and to practice presenting skills for those who will give a talk in a conference. Any topic related (but not restricted) to algorithms, combinatorics, and optimization is very welcome. You can share research results, present a work in progress or just share something of general interest. There will also be occasional survey talks by ACO faculty. The seminar currently meets on Fridays from 1pm to 2pm in Skiles 005, unless noted below, and some form of food/drinks will be provided. Thanks to ACO, ARC, and ISYE for their sponsorship.

Subscribe to the ACO Student Seminar mailing list.

Scheduled Talks


September 15: Peng Zhang, CS, Georgia Tech
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.


September 29: He Guo, Math, Georgia Tech
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.


October 6: Josh Daymude, Arizona State University/GaTech theory lab
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.


October 13: David Durfee, CS, Georgia Tech
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.


October 20: (11am at Skiles 005, ARC and Combinatorics) Mike Molloy, Department of Computer Science, University of Toronto
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}\).


November 3: (3pm at Skiles 005, Combinatorics) Joel Spencer, Department of Computer Science and Department of Mathematics, Courant Institute, New York University
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.



November 24 (Closed, Thanksgiving Break)



Contact

If you are interested in giving a talk at the seminar, you can contact any of the organizers: He Guo, Kevin Lai, Saurabh Sawlani or Guanyi Wang.

Other Semesters

Spring 2017; Fall 2016; Spring 2016; Fall 2015; Spring 2015; Fall 2014; Previous ones.