Seminars and Colloquia by Series

A Stochastic Approach to Shortcut Bridging in Programmable Matter

Series
ACO Student Seminar
Time
Friday, October 6, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Josh Daymude – Arizona State University/GaTech theory lab –
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.

Packing nearly optimal Ramsey R(3,t) Graphs

Series
ACO Student Seminar
Time
Friday, September 29, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
He Guo – School of Mathematics, Georgia Tech –
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.

Algorithm and Hardness for Linear Elasticity Problems

Series
ACO Student Seminar
Time
Friday, September 15, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peng Zhang – Computer Science, Georgia Tech –
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.

Cutoff for the random to random shuffle

Series
ACO Student Seminar
Time
Friday, April 28, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Megan Bernstein – School of Mathematics, Georgia Tech
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.

A random graph model for approximating sparse graphs

Series
ACO Student Seminar
Time
Friday, April 21, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Samantha Petti – School of Mathematics, Georgia Tech
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.

On concentration in discrete random processes

Series
ACO Student Seminar
Time
Friday, April 14, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Lutz Warnke – Georgia Institute of Technology
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.

Strategic Stable Marriage

Series
ACO Student Seminar
Time
Friday, April 7, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
James Bailey – Georgia Tech
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.

Test Sets for Nonnegativity of Reflection-Invariant Polynomials

Series
ACO Student Seminar
Time
Friday, March 31, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Jose Acevedo – School of Mathematics, Georgia Tech
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.

Communication-Efficient Decentralized and Stochastic Optimization

Series
ACO Student Seminar
Time
Friday, March 17, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Groseclose 402
Speaker
Soomin Lee – School of Industrial & Systems Engineering, Georgia Tech
Optimization problems arising in decentralized multi-agent systems have gained significant attention in the context of cyber-physical, communication, power, and robotic networks combined with privacy preservation, distributed data mining and processing issues. The distributed nature of the problems is inherent due to partial knowledge of the problem data (i.e., a portion of the cost function or a subset of the constraints is known to different entities in the system), which necessitates costly communications among neighboring agents. In this talk, we present a new class of decentralized first-order methods for nonsmooth and stochastic optimization problems which can significantly reduce the number of inter-node communications. Our major contribution is the development of decentralized communication sliding methods, which can skip inter-node communications while agents solve the primal subproblems iteratively through linearizations of their local objective functions.This is a joint work with Guanghui (George) Lan and Yi Zhou.

Hardness Results for Solving Graph-Structured Linear Systems

Series
ACO Student Seminar
Time
Friday, March 10, 2017 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Peng Zhang – College of Computing, Georgia Tech
Spielman and Teng (2004) showed that linear systems in Laplacian matrices can be solved in nearly linear time. Since then, a major research goal has been to develop fast solvers for linear systems in other classes of matrices. Recently, this has led to fast solvers for directed Laplacians (CKPPRSV'17) and connection Laplacians (KLPSS'16).Connection Laplacians are a special case of PSD-Graph-Structured Block Matrices (PGSBMs), block matrices whose non-zero structure correspond to a graph, and which additionally can be expressed as a sum of positive semi-definite matrices each corresponding to an edge in the graph. A major open question is whether fast solvers can be obtained for all PGSBMs (Spielman, 2016). Fast solvers for Connection Laplacians provided some hope for this. Other important families of matrices in the PGSBM class include truss stiffness matrices, which have many applications in engineering, and multi-commodity Laplacians, which arise when solving multi-commodity flow problems. In this talk, we show that multi-commodity and truss linear systems are unlikely to be solvable in nearly linear time, unless general linear systems (with integral coefficients) can be solved in nearly linear time. Joint work with Rasmus Kyng.

Pages