ACO Student Seminar
Spring 2015


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 1:00-2:00 PM in Skiles 005, and some form of food/drinks will be provided.

Scheduled Talks

January 9: Ben Cousins, Bypassing KLS: Gaussian Cooling and an O*(n3) Volume Algorithm

Abstract: We present an O*(n3) randomized algorithm for estimating the volume of a well-rounded convex body given by a membership oracle, improving on the previous best complexity of O*(n4). The new algorithmic ingredient is an accelerated cooling schedule where the rate of cooling increases with the temperature. Previously, the known approach for potentially achieving such complexity relied on a positive resolution of the KLS hyperplane conjecture, a central open problem in convex geometry. (joint work with Santosh Vempala)

January 16 (joint seminar with ARC): Peter Winkler, Pursuit on a Graph

Abstract: Pursuit games--motivated historically by military tactics--are a natural for graphical settings, and take many forms. We will present some recent results involving (among other things) drunks, Kakeya sets and a "ketchup graph." Lastly, we describe what we think is the most important open problem in the field.

February 27: Sarah Cannon, Phase Transitions in Random Dyadic Tilings and Rectangular Dissections

Abstract: We study rectangular dissections of an n by n lattice region into rectangles of area n. There is a natural edge-flipping Markov chain that we show connects this state space. A similar edge-flipping chain is already known to connect the state space when restricted to the subclass of dyadic tilings. While the mixing time of these chains remains open, we instead consider a weighted version of these Markov chains where, given a parameter w > 0, we would like to generate each rectangular dissection (or dyadic tiling) s with probability proportional to w^|s|, where |s| is the total edge length of dissection s. We give bounds on the mixing time of this edge-flip Markov chain in both the dyadic and general cases for nearly all values of w, and in the case of dyadic tilings demonstrate the existence of a sharp phase transition.

March 6: David Durfee, On the Complexity of Nash Equilibria in Anonymous Games

Abstract: Anonymous games, a class of succinctly representable multi-player games, have previously been shown to have a PTAS for computing approximate Nash equilibria, and computing exact Nash equilibria was conjectured to be hard. We show that the problem of finding an epsilon-approximate Nash equilibrium in an anonymous game with seven pure strategies is complete in PPAD, when the approximation parameter epsilon is exponentially small in the number of players.

March 13: Yan Wang, Induced Forests in Planar Bipartite Graphs

Abstract: Akiyama and Watanabe conjectured that every simple planar bipartite graph on n vertices contains an induced forest on at least 5n/8 vertices. We apply the discharging method to show that every simple bipartite planar graph on n vertices contains an induced forest on at least \lceil (4n + 3)/7 \rceil vertices.

March 20: No talk (Spring Break)
March 27: Arindam Khan, Improved Approximation for Vector Packing

Abstract: The d dimensional vector bin packing problem is a classical multidimensional generalization of bin packing problem where we are given a set of d-dimensional vectors with nonnegative entries and the goal is to pack these into a minimum number of bins so that for every bin the sum of packed vectors does not exceed the vectors of the bin in each dimension. The problem has numerous application in loading, scheduling, layout design. It has recently received renewed attention in connection with research on virtual machine placement in cloud computing.

We show a 1+ln(d/2) approximation algorithm for d-dimensional vector packing. We also show a 1+ ln(3/2) approximation algorithm for 2-dimensional vector packing. This is a joint work with Nikhil Bansal and Marek Elias at TU Eindhoven.

April 17: Cristóbal Guzmán, Bounding the density of packing objects: a symmetry-based optimization perspective

Abstract: How much of space can be filled with pairwise non-overlapping copies of a given solid? This is one of the oldest problems in mathematics, intriguing since the times of Aristotle, and remaining remarkably elusive until present times. For example, the three-dimensional sphere packing problem (posed by Kepler in 1611) was only solved in 1998 by Ferguson and Hales.

In this talk, I will provide some historical and modern applications of geometric packing problems, and I will introduce a methodology to derive upper bounds on the maximal density of such packings. These upper bounds are obtained by an infinite dimensional linear program, which is not computationally tractable. However, this problem can be approximated by using tools from sums of squares relaxations and symmetry reduction (harmonic analysis and representation theory), leading to rigorous computational upper bounds on the density.

Time permitting, I will present ongoing work with Maria Dostert, Fernando de Oliveira Filho and Frank Vallentin on the density of translative packings of superspheres (i.e., ell_p balls).

This is an introductory talk: no previous knowledge of sums of squares relaxations or symmetry reduction is assumed.

April 24: Aurko Roy, An LP inapproximability result for the non-uniform Balanced separator problem

Abstract: The non-uniform balanced separator problem is an optimization problem where we are given an edge weighted graph and a demand graph on the same vertex set. The objective is to find a minimum weight cut that separates roughly half the total demand. In this talk I will present a short proof that shows that no small Linear Program can approximate the non-uniform balanced separator problem independent of P vs NP or the Unique Games Conjecture. The main ingredient is a variant of a PCP theorem first proved by Khot and Vishnoi and known hardness results for the Sherali-Adams relaxation for the Unique Games problem due to Charikar and Makarychev. This is ongoing work with Sebastian Pokutta.


Contact

If you are interested in giving a talk at the seminar, you can contact either Emma Cohen or Ben Cousins.

Other Semesters

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