- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

We introduce the sparsified Cholesky and sparsified multigrid algorithms for solving systems of linear equations. These algorithms accelerate Gaussian elimination by sparsifying the nonzero matrix entries created by the elimination process.We use these new algorithms to derive the first nearly linear time algorithms for solving systems of equations in connection Laplacians, a generalization of Laplacian matrices that arise in many problems inimage and signal processing.We also prove that every connection Laplacian has a linear sized approximate inverse. This is an LU factorization with a linear number of nonzero entries that is a strong approximation of the originalmatrix. Using such a factorization one can solve systems of equations in a connection Laplacian in linear time. Such a factorization was unknown even for ordinary graph Laplacians.Joint work with Rasmus Kyng, Yin Tat Lee, Sushant Sachdeva, and Daniel Spielman. Manuscript at http://arxiv.org/abs/1512.01892.

Series: ACO Student Seminar

We consider perfect matchings of the square-octagon lattice, also known as``fortresses.'' There is a natural local Markov chain on the setof perfect matchings that is known to be ergodic. However, unlike Markov chains for sampling perfect matchings on the square and hexagonallattices, corresponding to domino and lozenge tilings, respectively, the seemingly relatedMarkov chain on the square-octagon lattice appears to converge slowly. Tounderstand why, we consider a weighted version of the problem.As with domino and lozenge tilings, it will be useful to view perfectmatchings on the square-octagon lattice in terms of sets of paths and cycleson a corresponding lattice region; here, the paths and cycles lie on theCartesian lattice and are required to turn left or right at every step. Forinput parameters $\lambda$ and $\mu$, we define the weight of a configurationto be $\lambda^{\abs{E(\sigma)}} \mu^{\abs{V(\sigma)}},$ where $E(\sigma)$ isthe 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 cyclesin $\sigma$. Weighted paths already come up in the reduction from perfectmatchings 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 whichthe chain converges slowly and another for which it is fast, suggesting a phasechange 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 mixingat $\lambda = 1$. Further, we show that for $\mu>1$, the Markov chain $\m$ is slowly mixingwhen $\lambda < \sqrt{\mu}/(2\sqrt{e})$ or $\lambda > 2\mu\sqrt{e}$. These arethe first rigorous proofs explaining why the natural local Markov chain can beslow for weighted fortresses or perfect matchings on thesquare-octagon lattice.

Series: ACO Student Seminar

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

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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

Series: ACO Student Seminar

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?

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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.