## Seminars and Colloquia by Series

Friday, April 28, 2017 - 13:05 , Location: Skiles 005 , Megan Bernstein , School of Mathematics, Georgia Tech , Organizer: Marcel Celaya
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.
Friday, April 21, 2017 - 13:05 , Location: Skiles 005 , Samantha Petti , School of Mathematics, Georgia Tech , Organizer: Marcel Celaya
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.
Friday, April 14, 2017 - 13:05 , Location: Skiles 005 , Lutz Warnke , Georgia Institute of Technology , Organizer: Marcel Celaya
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.
Friday, April 7, 2017 - 13:05 , Location: Skiles 005 , James Bailey , Georgia Tech , Organizer: Marcel Celaya
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.
Friday, March 31, 2017 - 13:05 , Location: Skiles 005 , Jose Acevedo , School of Mathematics, Georgia Tech , Organizer: Marcel Celaya
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.
Friday, March 17, 2017 - 13:05 , Location: Groseclose 402 , Soomin Lee , School of Industrial & Systems Engineering, Georgia Tech , Organizer: Marcel Celaya
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.
Friday, March 10, 2017 - 13:05 , Location: Skiles 005 , Peng Zhang , College of Computing, Georgia Tech , Organizer: Marcel Celaya
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.
Friday, February 17, 2017 - 13:05 , Location: Skiles 005 , David Durfee , College of Computing, Georgia Tech , Organizer: Marcel Celaya
We present an algorithm that, with high probability, generates a random spanning treefrom an edge-weighted undirected graph in O (n^{5/3}m^{1/3}) time. The tree is sampled from adistribution 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 thebest 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., butwe 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 ispreserved 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 Sof vertex pairs via approximate Schur complements in O (m + (n + |S|)/\eps^{ −2}) time, without usingthe 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
Friday, February 10, 2017 - 13:05 , Location: Skiles 005 , , College of Computing, Georgia Tech , Organizer: Marcel Celaya
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.
Friday, December 2, 2016 - 13:05 , Location: Skiles 006 , Daniel Zink , Georgia Tech , Organizer: Marcel Celaya
Conditional gradient algorithms (also often called Frank-Wolfe algorithms) are popular due to their simplicity of only requiring a linear optimization oracle and more recently they also gained significant traction for online learning. While simple in principle, in many cases the actual implementation of the linear optimization oracle is costly. We show a general method to lazify various conditional gradient algorithms, which in actual computations leads to several orders of magnitude of speedup in wall-clock time. This is achieved by using a faster separation oracle instead of a linear optimization oracle, relying only on few linear optimization oracle calls.