# ACO Student Seminar Fall 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 1pm to 2pm in Skiles 005 and some form of food/drinks will be provided.

## Scheduled Talks

September 11: Chun-Hung Liu, 3-coloring H-minor-free graphs with no large monochromatic components

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.

September 25 : Sarah Cannon, Sampling on lattices with free boundary conditions using randomized extensions

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

October 9: Arefin Huq, The matching problem has no small symmetric SDP

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.

October 23: Kevin Lai, Label optimal regret bounds for online local learning; Anna Kirkpatrick, The Complexity of Counting Poset and Permutation Patterns

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?

October 30: Alejandro Toriello, Semi-Infinite Relaxations for a Dynamic Knapsack Problem with Stochastic Item Sizes

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

November 6: Troy Retter, Folkman Numbers

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.

November 13: Marcel Celaya, On the linear span of lattice points in a parallelepiped

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.

November 20: Sadra Yazdanbod, A Market for Scheduling, with Applications to Cloud Computing

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

December 4: Prateek Bhakta, Sampling weighted perfect matchings on the square octagon lattice

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.

## Contact

If you are interested in giving a talk at the seminar, you can contact any of the organizers: Sarah Cannon or Yan Wang.

## Other Semesters

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