ACO Student Seminar
Spring 2017


Description

The Georgia Tech ACO Student Seminar is run by students in the ACO program. The objective of the seminar is to give students and postdocs a forum to share their research results or present 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.

Scheduled Talks

February 10: Sarah Cannon, Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings

Abstract: We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall, and Spencer in 2002. The technique used, adapted from spin system analysis in statistical physics and not widely used in computer science literature, involves a multilevel decomposition of the state space and is of independent interest. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2^{-s}, (a+1)2^{-s}] x [b2^{-t}, (b+1)2^{-t}] for non-negative integers a,b,s,t. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n^{4.09}), which implies that the mixing time is at most O(n^{5.09}). We complement this by showing that the relaxation time is at least \Omega(n^{1.38}), improving upon the previously best lower bound of \Omega(n log n) coming from the diameter of the chain. This is joint work with David Levin and Alexandre Stauffer.

February 17: David Durfee, Sampling Random Spanning Trees Faster than Matrix Multiplication

Abstract: We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in O (n^{5/3}m^{1/3}) time. The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(n^\omega). For the special case of unweighted graphs, this improves upon the best previously known running time of ˜O(min{n^\omega, mn^{1/2}, m^{4/3}}) for m >> n^{7/4} (Colbourn et al. ’96, Kelner-Madry ’09, Madry et al. ’15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement).

As part of our algorithm, we show how to compute -approximate effective resistances for a set S of vertex pairs via approximate Schur complements in O (m + (n + |S|)/\eps^{ −2}) time, without using the Johnson-Lindenstrauss lemma which requires eO(min{(m+|S|) \eps{−2},m+n /eps^{−4} +|S|/eps^{ −2}}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn’t sufficiently accurate.

Joint work with Rasmus Kyng, John Peebles, Anup Rao, and Sushant Sachdeva
March 10: Peng Zhang, Hardness Results for Solving Graph-Structured Linear Systems

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

March 17: Soomin Lee, Communication-Efficient Decentralized and Stochastic Optimization

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

March 31: Jose Acevedo, Test Sets for Nonnegativity of Reflection-Invariant Polynomials

Abstract: In this talk we will show that, among real polynomials which are invariant under the action of a finite reflection group, a large family of them, either low degree or sparse, are globally nonnegative provided they are nonnegative on the hyperplane arrangement (our test set) associated to the reflection group. We explore stronger conditions on the degree and the sparsity that reduce the size of the test set, as it happens for the particular case of symmetric polynomials.

April 7: James Bailey, Strategic Stable Marriage

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

April 14: Lutz Warnke, On concentration in discrete random processes

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

April 21: Samantha Petti, A random graph model for approximating sparse graphs

Abstract: Beginning with Szemeredi’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.

April 28: Megan Bernstein, Cutoff for the random to random shuffle

Abstract: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 Nestoridi


Contact

If you are interested in giving a talk at the seminar, you can contact any of the organizers: Digvijay Boob, Marcel Celaya, or David Durfee.

Other Semesters

Fall 2016; Spring 2016; Fall 2015; Spring 2015; Fall 2014