Seminars and Colloquia by Series

Friday, October 14, 2016 - 13:00 , Location: Skiles 005 , Matthew Fahrbach , College of Computing, Georgia Tech , Organizer: Marcel Celaya
Graded posets are partially ordered sets equipped with a unique rank function that respects the partial order and such that neighboring elements in the Hasse diagram have ranks that differ by one. We frequently find them throughout combinatorics, including the canonical partial order on Young diagrams and plane partitions, where their respective rank functions are the area and volume under the configuration. We ask when it is possible to efficiently sample elements with a fixed rank in a graded poset. We show that for certain classes of posets, a biased Markov chain that connects elements in the Hasse diagram allows us to approximately generate samples from any fixed rank in expected polynomial time. While varying a bias parameter to increase the likelihood of a sample of a desired size is common in statistical physics, one typically needs properties such as log-concavity in the number of elements of each size to generate desired samples with sufficiently high probability. Here we do not even require unimodality in order to guarantee that the algorithm succeeds in generating samples of the desired rank efficiently. This joint work with Prateek Bhakta, Ben Cousins, and Dana Randall will appear at SODA 2017. 
Friday, September 23, 2016 - 13:05 , Location: Skiles 005 , Richard Peng , College of Computing, Georgia Tech , Organizer: Marcel Celaya
Parallel algorithms study ways of speeding up sequential algorithms by splitting work onto multiple processors. Theoretical studies of parallel algorithms often focus on performing a small number of operations, but assume more generous models of communication. Recent progresses led to parallel algorithms for many graph optimization problems that have proven to be difficult to parallelize. In this talk I will survey routines at the core of these results: low diameter decompositions, random sampling, and iterative methods.
Friday, September 16, 2016 - 13:05 , Location: Skiles 005 , Sarah Cannon , Georgia Tech , , Organizer: Marcel Celaya
I will present work on a new application of Markov chains to distributed computing. Motivated by programmable matter and the behavior of biological distributed systems such as ant colonies, the geometric amoebot model abstracts these processes as self-organizing particle systems where particles with limited computational power move on the triangular lattice. Previous algorithms developed in this setting have relied heavily on leader election, tree structures that are not robust to failures, and persistent memory. We developed a distributed algorithm for the compression problem, where all particles want to gather together as tightly as possible, that is based on a Markov chain and is simple, robust, and oblivious. Tools from Markov chain analysis enable rigorous proofs about its behavior, and we show compression will occur with high probability. This joint work with Joshua J. Daymude, Dana Randall, and Andrea Richa appeared at PODC 2016. I will also present some more recent extensions of this approach to other problems, which is joint work with Marta Andres Arroyo as well.
Friday, April 22, 2016 - 13:05 , Location: Skiles 005 , David Durfee , Georgia Tech , Organizer: Yan Wang
We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a $(1 \pm \epsilon)$-spectral sparsifier with amortized update time $poly(\log{n},\epsilon^{-1})$. Second, we give a fully dynamic algorithm for maintaining a $(1 \pm \epsilon)$-cut sparsifier with worst-case update time $poly(\log{n},\epsilon^{-1})$. Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a $(1 + \epsilon)$-approximate minimum cut in an unweighted, undirected, bipartite graph with amortized update time $poly(\log{n},\epsilon^{-1})$.Joint work with Ittai Abraham, Ioannis Koutis, Sebastian Krinninger, and Richard Peng
Friday, April 15, 2016 - 13:05 , Location: Skiles 005 , Daniel Blado , Georgia Tech , Organizer: Yan Wang
We examine a variant of the knapsack problem in which item sizes are random according to an arbitrary but known distribution. In each iteration, an item size is realized once the decision maker chooses and attempts to insert an item. With the aim of maximizing the expected profit, the process ends when either all items are successfully inserted or a failed insertion occurs. We investigate the strength of a particular dynamic programming based LP bound by examining its gap with the optimal adaptive policy. Our new relaxation is based on a quadratic value function approximation which introduces the notion of diminishing returns by encoding interactions between remaining items. We compare the bound to previous bounds in literature, including the best known pseudopolynomial bound, and contrast their corresponding policies with two natural greedy policies. Our main conclusion is that the quadratic bound is theoretically more efficient than the pseudopolyomial bound yet empirically comparable to it in both value and running time.
Friday, April 8, 2016 - 13:05 , Location: Skiles 005 , Samantha Petti , Georgia Tech , Organizer: Yan Wang
Motivated by neurally feasible computation, we study Boolean functions of an arbitrary number of input variables that can be realized by recursively applying a small set of functions with a constant number of inputs each. This restricted type of construction is neurally feasible since it uses little global coordination or control. Valiant’s construction of a majority function can be realized in this manner and, as we show, can be generalized to any uniform threshold function. We study the rate of convergence, finding that while linear convergence to the correct function can be achieved for any threshold using a fixed set of primitives, for quadratic convergence, the size of the primitives must grow as the threshold approaches 0 or 1. We also study finite realizations of this process, and show that the constructions realized are accurate outside a small interval near the target threshold, where the size of the construction at each level grows as the inverse square of the interval width. This phenomenon, that errors are higher closer to thresholds (and thresholds closer to the boundary are harder to represent), is also a well-known cognitive finding. Finally, we give a neurally feasible algorithm that uses recursive constructions to learn threshold functions. This is joint work with Christos Papadimitriou and Santosh Vempala.
Friday, April 1, 2016 - 13:05 , Location: Skiles 005 , Hao Huang , Emory University , Organizer: Yan Wang
A Ruzsa-Szemeredi graph is a graph on n vertices whose edge set can be partitioned into induced matchings of size cn. The study of these graphs goes back more than 35 years and has connections with number theory, combinatorics, complexity theory and information theory. In this talk we will discuss the history and some recent developments in this area. In particular, we show that when c>1/4, there can be only constantly many matchings. On the other hand, for c=1/4, the maximum number of induced matchings is logarithmic in n. This is joint work with Jacob Fox and Benny Sudakov.
Friday, March 18, 2016 - 13:05 , Location: Skiles 005 , Chi Ho Yuen , Georgia Tech , Organizer: Yan Wang
This talk aims to give a glimpse into the theory of divisors on graphs in tropical geometry, and its recent application in bijective combinatorics. I will start by introducing basic notions and results of the subject. Then I will mention some of its connections with other fields in math. Finally I will talk about my own work on how tropical geometry leads to an unexpectedly simple class of bijections between spanning trees of a graph and its sandpile group.
Friday, March 11, 2016 - 13:05 , Location: Skiles 256 , Rui Gao , Georgia Tech , Organizer: Yan Wang
Stochastic programming is a powerful approach for decision-making under uncertainty. Unfortunately, the solution may be misleading if the underlying distribution of the involved random parameters is not known exactly. In this talk, we study distributionally robust stochastic programming (DRSP), in which the decision hedges against the worst possible distribution that belongs to an ambiguity set. More specifically, we consider the DRSP with the ambiguity set comprising all distributions that are close to some reference distribution in terms of Wasserstein distance. We derive a tractable reformulation of the DRSP problem by constructing the worst-case distribution explicitly via the first-order optimality condition of the dual problem. Our approach has several theoretical and computational implications. First, using the precise characterization of the worst-case distribution, we show that the DRSP can be approximated by robust programs to arbitrary accuracy, and thus many DRSP problems become tractable with tools from robust optimization. Second, when the objective is concave in the uncertainty, the robust-program approximation is exact and equivalent to a saddle-point problem, which can be solved by a Mirror-Prox algorithm. Third, our framework can also be applied to problems other than stochastic programming, such as a class of distributionally robust transportation problems. Furthermore, we perform sensitivity analysis with respect to the radius of the Wasserstein ball, and apply our results to the newsvendor problem, two-stage linear program with uncertainty-affected recourse, and worst-case Value-at-risk analysis.
Friday, March 4, 2016 - 13:05 , Location: Skiles 256 , Ben Cousins , Georgia Tech , Organizer: Yan Wang
I will give a tour of high-dimensional sampling algorithms, both from a theoretical and applied perspective, for generating random samples from a convex body. There are many well-studied random walks to choose from, with many of them having rigorous mixing bounds which say when the random walk has converged. We then show that the techniques from theory yield state-of-the-art algorithms in practice, where we analyze various organisms by randomly sampling their metabolic networks.This work is in collaboration with Ronan Fleming, Hulda Haraldsdottir ,and Santosh Vempala.