Spring 2015

**Abstract**:
We present an O*(n^{3}) 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*(n^{4}).
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.

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

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

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