Fall 2015

**Abstract:**
A graph is a minor of another graph if the former can be obtained
from a subgraph of the latter by contracting edges. We prove that for
every graph H, if H is not a minor of a graph G, then V(G) can be
3-colored such that the subgraph induced by each color class has no
component with size greater than a function of H and the maximum degree
of G. This answers a question raised by Esperet and Joret, generalizes
their result for 3-coloring V(G) for graphs G embeddable in a fixed
surface, and improves a result of Alon, Ding, Oporowski and Vertigan for
4-coloringing V(G) for H-minor free graphs G. As a corollary, we prove
that for every positive integer t, if G is a graph with no K_{t+1}
minor, then V(G) can be 3t-colored such that the subgraph induced by
each color class has no component with size larger than a function of t.
This improves a result of Wood for coloring V(G) by 3.5t+2 colors. This
work is joint with Sang-il Oum.

**Abstract:**
Many statistical physics models are defined on an infinite lattice by taking appropriate limits
of the model on finite lattice regions. A key consideration is which boundary to use when taking
these limits, since the boundary can have significant influence on properties of the limit. Fixed
boundary conditions assume that the boundary cells are given a fixed assignment, and free boundary
conditions allow these cells to vary, taking the union of all possible fixed boundaries. It is known
that these two boundary conditions can cause significant differences in physical properties, such as
whether there is a phase transition, as well as computational properties, including whether local
Markov chain algorithms used to sample and approximately count are efficient.

We consider configurations with free or partially free boundary conditions and show that by
randomly extending the boundary by a few layers, choosing among only a constant number of
allowable extensions, we can generalize the arguments used in the fixed boundary setting to infer
bounds on the mixing time for free boundaries. We demonstrate this principled approach using
randomized extensions for 3-colorings of regions of Z^{2} and lozenge tilings of regions of the triangle
lattice, building on arguments for the fixed boundary cases due to Luby et.al. Our approach
yields an efficient algorithm for sampling free boundary 3-colorings of regions with one reflex corner,
the first result to efficiently sample free boundary 3-colorings of any nonconvex region. We also
consider self-reducibility of free boundary 3-colorings of rectangles, and show our algorithm can be
used to approximately count the number of free-boundary 3-colorings of a rectangle.

This is joint work with Dana Randall.

**Abstract:** Yannakakis showed that the matching problem
does not have a small symmetric linear program. Rothvoß recently proved
that any (not necessarily symmetric) linear program also has exponential
size. It is natural to ask whether the matching problem can be
expressed compactly in a framework such as semidefinite programming
(SDP) that is more powerful than linear programming but still allows
efficient optimization. We answer this question negatively for symmetric
SDPs: any symmetric SDP for the matching problem has exponential size.
We also show that an O(k)-round Lasserre SDP relaxation for the metric
traveling salesperson problem (TSP) yields at least as good an
approximation as any symmetric SDP relaxation of size n^k. The key
technical ingredient underlying both these results is an upper bound on
the degree needed to derive polynomial identities that hold over the
space of matchings or traveling salesperson tours.

This is joint work with Jonah Brown-Cohen, Prasad Raghavendra and
Benjamin Weitz from Berkeley, and Gabor Braun, Sebastian Pokutta, Aurko
Roy and Daniel Zink at Georgia Tech.

**Abstract (Kevin Lai):** We resolve an open question from
(Christiano, 2014b) posed in COLT'14 regarding the optimal dependency of
the regret achievable for online local learning on the size of the
label set. In this framework the algorithm is shown a pair of items at
each step, chosen from a set of n items. The learner then predicts a
label for each item, from a label set of size L and receives a real
valued payoff. This is a natural framework which captures many
interesting scenarios such as collaborative filtering, online gambling,
and online max cut among others. (Christiano, 2014a) designed an
efficient online learning algorithm for this problem achieving a regret
of O((nL^3T)^(1/2)), where T is the number of rounds. Information
theoretically, one can achieve a regret of O((n log LT)^(1/2)). One of
the main open questions left in this framework concerns closing the
above gap.

In this work, we provide a complete answer to the question above via two
main results. We show, via a tighter analysis, that the semi-definite
programming based algorithm of (Christiano, 2014a), in fact achieves a
regret of O((nLT)^(1/2)). Second, we show a matching computational lower
bound. Namely, we show that a polynomial time algorithm for online
local learning with lower regret would imply a polynomial time algorithm
for the planted clique problem which is widely believed to be hard. We
prove a similar hardness result under a related conjecture concerning
planted dense subgraphs that we put forth. Unlike planted clique, the
planted dense subgraph problem does not have any known quasi-polynomial
time algorithms. Computational lower bounds for online learning are
relatively rare, and we hope that the ideas developed in this work will
lead to lower bounds for other online learning scenarios as well.

Joint work with Pranjal Awasthi, Moses Charikar, and Andrej Risteski at Princeton.

**Abstract (Anna Kirkpatrick):** We introduce a notion of pattern
occurrence that generalizes both classical permutation patterns as well
as poset containment. Many questions about pattern statistics and
avoidance generalize naturally to this setting, and we focus on
functional complexity problems – particularly those that arise by
constraining the order dimensions of the pattern and text posets. We
show that counting the number of induced, injective occurrences among
dimension 2 posets is #P-hard; enumerating the linear extensions that
occur in realizers of dimension 2 posets can be done in polynomial time,
while for unconstrained dimension it is GI-complete; counting not
necessarily induced, injective occurrences among dimension 2 posets is
#P-hard; counting injective or not necessarily injective occurrences of
an arbitrary pattern in a dimension 1 text is #P-hard, although it is in
FP if the pattern poset is constrained to have bounded intrinsic width;
and counting injective occurrences of a dimension 1 pattern in an
arbitrary text is #P-hard, while it is in FP for bounded dimension
texts. This framework easily leads to a number of open questions, chief
among which are (1) is it #P-hard to count the number of occurrences of a
dimension 2 pattern in a dimension 1 text, and (2) is it #P-hard to
count the number of texts which avoid a given pattern?

**Abstract:** We consider a version of the knapsack problem in
which an item size is random and revealed only when the decision maker
attempts to insert it. After every successful insertion the decision
maker can choose the next item dynamically based on the remaining
capacity and available items, while an unsuccessful insertion terminates
the process. We propose a new semi-infinite relaxation based on an
affine value function approximation, and show that an existing
pseudo-polynomial relaxation corresponds to a non-parametric value
function approximation. We compare both theoretically to other
relaxations from the literature and also perform a computational study.
Our new relaxation provides tight bounds over a variety of different
instances and surprisingly becomes tighter as the number of items
increases.

Joint work with Daniel Blado (ACO) and Weihong Hu (ISyE).

**Abstract:** For an integer k, the Folkman number f(k) is the
least integer n for which there exists a graph G on n vertices that
does not contain a clique of size k and has the property that every two
coloring of E(G) yields a monochromatic clique of size of size k. That
is, it is the least number of vertices in a K_{k+1}-free graph that is
Ramsey to K_k. A recent result of Rodl, Rucinski, and Schacht gives an
upper bound on the Folkman numbers f(k) which is exponential in k. A
fundamental tool in their proof is a theorem of Saxton and Thomason on
hypergraph containers. This talk will give a brief history of the
Folkman numbers, introduce the hypergraph container theorem, and sketch
the proof of the Rodl, Rucinski, and Schacht result. Recent work with
Hiep Han, Vojtech Rodl, and Mathias Schacht on two related problems
concerning cycles in graphs and arithmetic progressions in subset of the
integers will also be presented.

**Abstract:** We find a good characterization for the
following problem: Given a rational row vector c and a lattice L in R^n
which contains the integer lattice Z^n, do all lattice points of L in
the half-open unit cube [0,1)^n lie on the hyperplane {x in R^n : cx =
0}? This work generalizes a theorem due to G. K. White, which provides
sufficient and necessary conditions for a tetrahedron in R^3 with
integral vertices to have no other integral points. Our approach is
based on a novel proof of White's result using number-theoretic
techniques due to Morrison and Stevens. In this talk, we illustrate some
of the ideas and describe some applications of this problem.

**Abstract:**
We present a market for allocating and scheduling resources to
agents who have specified budgets and need to complete specific tasks.
Two important aspects required in this market are:

(1) agents need specific amounts of each resource to complete their tasks, and

(2) agents would like to complete their tasks as soon as possible.

In incorporating these aspects, we arrive at a model that deviates
substantially from market models studied so far in economics and
theoretical computer science. Indeed, all known techniques developed to
compute equilibria in markets in the last decade and half seem not to
apply here.

We give a polynomial time algorithm for computing an equilibrium using a
new technique that is somewhat reminiscent of the ''ironing" procedure
used in the characterization of optimal auctions by Myerson. This is
inspite of the fact that the set of equilibrium prices could be
non-convex; in fact it could have ''holes''. Our market model is
motivated by the cloud computing marketplace. Even though this market is
already huge and is projected to grow at a massive rate, it is
currently run in an ad hoc manner.

Joint work with: Nikhil Devanur, Jugal Garg, Ruta Mehta, Vijay V. Vazirani

**Abstract:** We consider perfect matchings of the square-octagon lattice, also known as
``fortresses.'' There is a natural local Markov chain on the set
of perfect matchings that is known to be ergodic. However, unlike
Markov chains for sampling perfect matchings on the square and hexagonal
lattices, corresponding to domino and lozenge tilings, respectively, the seemingly related
Markov chain on the square-octagon lattice appears to converge slowly. To
understand why, we consider a weighted version of the problem.
As with domino and lozenge tilings, it will be useful to view perfect
matchings on the square-octagon lattice in terms of sets of paths and cycles
on a corresponding lattice region; here, the paths and cycles lie on the
Cartesian lattice and are required to turn left or right at every step. For
input parameters $\lambda$ and $\mu$, we define the weight of a configuration
to be $\lambda^{\abs{E(\sigma)}} \mu^{\abs{V(\sigma)}},$ where $E(\sigma)$ is
the total number of edges on the paths and cycles of $\sigma$ and $V(\sigma)$
is the number of vertices that are not incident to any of the paths or cycles
in $\sigma$. Weighted paths already come up in the reduction from perfect
matchings to turning lattice paths, corresponding to the case when $\lambda=1$
and $\mu = 2$.

First, fixing $\mu=1$, we show that there are choices of~$\lambda$ for which
the chain converges slowly and another for which it is fast, suggesting a phase
change in the mixing time. More precisely,
the chain requires exponential time (in the size of the lattice region) when
$\lambda < 1/(2\sqrt{e})$ or $\lambda >2\sqrt{e}$, while it is polynomially mixing
at $\lambda = 1$. Further, we show that for $\mu>1$, the Markov chain $\m$ is slowly mixing
when $\lambda < \sqrt{\mu}/(2\sqrt{e})$ or $\lambda > 2\mu\sqrt{e}$. These are
the first rigorous proofs explaining why the natural local Markov chain can be
slow for weighted fortresses or perfect matchings on the
square-octagon lattice.