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)
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.
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.
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.
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.
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
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.
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.
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.