# 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

### Spring 2018

January 19: Sarah Cannon, CS, Georgia Tech
Markov Chains and Emergent Behavior

Abstract: Studying random samples drawn from large, complex sets is one way to begin to learn about typical properties and behaviors. However, it is important that the samples examined are random enough: studying samples that are unexpectedly correlated or drawn from the wrong distribution can produce misleading conclusions. Sampling processes using Markov chains have been utilized in physics, chemistry, and computer science, among other fields, but they are often applied without careful analysis of their reliability. Making sure widely-used sampling processes produce reliably representative samples is a main focus of my research, and in this talk I'll touch on two specific applications from statistical physics and combinatorics.

I'll also discuss work applying these same Markov chain processes used for sampling in a novel way to address research questions in programmable matter and swarm robotics, where a main goal is to understand how simple computational elements can accomplish complicated system-level goals. In a constrained setting, we've answered this question by showing that groups of abstract particles executing our simple processes (which are derived from Markov chains) can provably accomplish remarkable global objectives. In the long run, one goal is to understand the minimum computational abilities elements need in order to exhibit complex global behavior, with an eye towards developing systems where individual components are as simple as possible.

This talk includes joint work with Marta Andrés Arroyo, Joshua J. Daymude, Daniel I. Goldman, David A. Levin, Shengkai Li, Dana Randall, Andréa Richa, William Savoie, Alexandre Stauffer, and Ross Warkentin.

January 26: David Hemmi, CS, Monash University
High-level modelling and solving of combinatorial stochastic programs

Abstract: Stochastic programming is concerned with decision making under uncertainty, seeking an optimal policy with respect to a set of possible future scenarios. While the value of Stochastic Programming is obvious to many practitioners, in reality uncertainty in decision making is oftentimes neglected.

For deterministic optimisation problems, a coherent chain of modelling and solving exists. Employing standard modelling languages and solvers for stochastic programs is however difficult. First, they have (with exceptions) no native support to formulate Stochastic Programs. Secondly solving stochastic programs with standard solvers (e.g. MIP solvers) is often computationally intractable.

David will be talking about his research that aims to make Stochastic Programming more accessible. First, he will be talking about modelling deterministic and stochastic programs in the Constraint Programming language MiniZinc - a modelling paradigm that retains the structure of a problem much more strongly than MIP formulations. Secondly, he will be talking about decomposition algorithms he has been working on to solve combinatorial Stochastic Programs.

Bio:
David is a PhD student at Monash University in Melbourne. Before joining Monash, he completed a Bachelors degree in Systems Engineering in Switzerland, studied Robotics at University of Bristol and worked in various engineering roles. As part of his Phd, David is working on a solver system for stochastic combinatorial optimisation problems that are modelled in in the Constraint Programming language MiniZinc. In future, he would like to combine his passion for automation with the research he is doing in operations research.

February 2: (Skiles 006, 1-2 pm) Audra McMillan, Math, University of Michigan
Local Differential Privacy for Physical Sensor Data and Sparse Recovery

Abstract: Physical sensors (thermal, light, motion, etc.) are becoming ubiquitous and offer important benefits to society. However, allowing sensors into our private spaces has resulted in considerable privacy concerns. Differential privacy has been developed to help alleviate these privacy concerns. In this talk, we’ll develop and define a framework for releasing physical data that preserves both utility and provides privacy. Our notion of closeness of physical data will be defined via the Earth Mover Distance and we’ll discuss the implications of this choice. Physical data, such as temperature distributions, are often only accessible to us via a linear transformation of the data.

We’ll analyse the implications of our privacy definition for linear inverse problems, focusing on those that are traditionally considered to be "ill-conditioned”. We’ll then instantiate our framework with the heat kernel on graphs and discuss how the privacy parameter relates to the connectivity of the graph. Our work indicates that it is possible to produce locally private sensor measurements that both keep the exact locations of the heat sources private and permit recovery of the general geographic vicinity'' of the sources. Joint work with Anna C. Gilbert.

February 9: (Joint with ARC Colloquium) Greg Bodwin, CS, MIT
The Distance Oracle Hierarchy

Abstract: A lot of well-studied problems in CS Theory are about making “sketches” of graphs that occupy much less space than the graph itself, but where the shortest path distances of the graph can still be approximately recovered from the sketch. For example, in the literature on Spanners, we seek a sparse subgraph whose distance metric approximates that of the original graph. In Emulator literature, we relax the requirement that the approximating graph is a subgraph. Most generally, in Distance Oracles, the sketch can be an arbitrary data structure, so long as it can approximately answer queries about the pairwise distance between nodes in the original graph.

Research on these objects typically focuses on optimizing the worst-case tradeoff between the quality of the approximation and the amount of space that the sketch occupies. In this talk, we will survey a recent leap in understanding about this tradeoff, overturning the conventional wisdom on the problem. Specifically, the tradeoff is not smooth, but rather it follows a new discrete hierarchy in which the quality of the approximation that can be obtained jumps considerably at certain predictable size thresholds. The proof is graph-theoretic and relies on building large families of graphs with large discrepancies in their metrics.

March 16: Gramoz Goranci, CS, University of Vienna
Fully Dynamic Low-Diameter Decomposition with Applications

Abstract: A low-diameter decomposition (LDD) of an undirected graph G is a partitioning of G into components of bounded diameter, such that only a small fraction of original edges are between the components. This decomposition has played instrumental role in the design of low-stretch spanning tree, spanners, distributed algorithms etc.

A natural question is whether such a decomposition can be efficiently maintained/updated as G undergoes insertions/deletions of edges. We make the first step towards answering this question by designing a fully-dynamic graph algorithm that maintains an LDD in sub-linear update time.

It is known that any undirected graph G admits a spanning tree T with nearly logarithmic average stretch, which can be computed in nearly linear-time. This tree decomposition underlies many recent progress in static algorithms for combinatorial and scientific flows. Using our dynamic LDD algorithm, we present the first non-trivial algorithm that dynamically maintains a low-stretch spanning tree in $$\tilde{O}(t^2)$$ amortized update time, while achieving $$(t + \sqrt{n^{1+o(1)}/t})$$ stretch, for every $$1 \leq t \leq n$$.

Joint work with Sebastian Krinninger.

March 23: Closed, Spring Break

April 6: Uthaipon (Tao) Tantipongpipat, Georgia Tech
Approximation algorithms for optimal design problems

Abstract: The talk is based on https://arxiv.org/abs/1802.08318.

April 20: Kira Goldner, CSE, University of Washington
Selling Partially-Ordered Items: Exploring the Space between Single- and Multi-Dimensional Mechanism Design

Abstract: Consider the problem of selling items to a unit-demand buyer. Most work on maximizing seller revenue considers either a setting that is single dimensional, such as where the items are identical, or multi-dimensional, where the items are heterogeneous. With respect to revenue-optimal mechanisms, these settings sit at extreme ends of a spectrum: from simple and fully characterized (single-dimensional) to complex and nebulous (multi-dimensional).

In this paper, we identify a setting that sits in between these extremes. We consider a seller who has three services {A,B,C} for sale to a single buyer with a value v and an interest G from {A,B,C}, and there is a known partial ordering over the services. For example, suppose the seller is selling {internet}, {internet, phone}, and {internet, cable tv}. A buyer with interest {internet} would be satisfied by receiving phone or cable tv in addition, but a customer whose interest is {internet, phone} cannot be satisfied by any other option. Thus this corresponds to a partial-ordering where {internet} > {internet, phone} and {internet} > {internet, cable tv}, but {internet, phone} and {internet, cable tv} are not comparable.

We show formally that partially-ordered items lie in a space of their own, in between identical and heterogeneous items: there exist distributions over (value, interest) pairs for three partially-ordered items such that the menu complexity of the optimal mechanism is unbounded, yet for all distributions there exists an optimal mechanism of finite menu complexity. So this setting is vastly more complex than identical items (where the menu complexity is one), or even “totally-ordered” items as in the FedEx Problem [FGKK16] (where the menu complexity is at most seven, for three items), yet drastically more structured than heterogeneous items (where the menu complexity can be uncountable [DDT15]). We achieve this result by proving a characterization of the class of best duals and by giving a primal recovery algorithm which obtains the optimal mechanism. In addition, we (1) extend our lower-bound to the Multi-Unit Pricing setting, (2) give a tighter and deterministic characterization of the optimal mechanism when the buyer’s distribution satisfies the declining marginal revenue condition, and (3) prove a master theorem that allows us to reason about duals instead of distributions.

Joint work with Nikhil Devanur, Raghuvansh Saxena, Ariel Schvartzman, and Matt Weinberg.

Kira will be around all week. Please email her to schedule one-on-one meetings.

### Fall 2017

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 (vedio)

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!) (vedio)

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.