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

Series: ACO Student Seminar

We examine a variant of the knapsack problem in which item sizes are
random according to an arbitrary but known distribution. In each
iteration, an item size is realized once the decision maker chooses and
attempts to insert an item. With the aim of maximizing the expected
profit, the process ends when either all items are successfully inserted
or a failed insertion occurs. We investigate the strength of a
particular dynamic programming based LP bound by examining its gap with
the optimal adaptive policy. Our new relaxation is based on a quadratic
value function approximation which introduces the notion of diminishing
returns by encoding interactions between remaining items. We compare the
bound to previous bounds in literature, including the best known
pseudopolynomial bound, and contrast their corresponding policies with
two natural greedy policies. Our main conclusion is that the quadratic
bound is theoretically more efficient than the pseudopolyomial bound yet
empirically comparable to it in both value and running time.

Series: ACO Student Seminar

Motivated by neurally feasible computation, we study Boolean functions
of an arbitrary number of input variables that can be realized by
recursively applying a small set of functions with a constant number of
inputs each. This restricted type of construction is neurally feasible
since it uses little global coordination or control. Valiant’s
construction of a majority function can be realized in this manner and,
as we show, can be generalized to any uniform threshold function. We
study the rate of convergence, finding that while linear convergence to
the correct function can be achieved for any threshold using a fixed set
of primitives, for quadratic convergence, the size of the primitives
must grow as the threshold approaches 0 or 1. We also study finite
realizations of this process, and show that the constructions realized
are accurate outside a small interval near the target threshold, where
the size of the construction at each level grows as the inverse square
of the interval width. This phenomenon, that errors are higher closer to
thresholds (and thresholds closer to the boundary are harder to
represent), is also a well-known cognitive finding. Finally, we give a
neurally feasible algorithm that uses recursive constructions to learn
threshold functions. This is joint work with Christos Papadimitriou and
Santosh Vempala.

Series: ACO Student Seminar

A Ruzsa-Szemeredi graph is a graph on n vertices whose edge set can be partitioned into induced matchings of size cn. The study of these graphs goes back more than 35 years and has connections with number theory, combinatorics, complexity theory and information theory. In this talk we will discuss the history and some recent developments in this area. In particular, we show that when c>1/4, there can be only constantly many matchings. On the other hand, for c=1/4, the maximum number of induced matchings is logarithmic in n. This is joint work with Jacob Fox and Benny Sudakov.

Series: ACO Student Seminar

This talk aims to give a glimpse into the theory of divisors on graphs in tropical geometry, and its recent application in bijective combinatorics. I will start by introducing basic notions and results of the subject. Then I will mention some of its connections with other fields in math. Finally I will talk about my own work on how tropical geometry leads to an unexpectedly simple class of bijections between spanning trees of a graph and its sandpile group.

Series: ACO Student Seminar

Stochastic programming is a powerful
approach for decision-making under uncertainty. Unfortunately, the solution may
be misleading if the underlying distribution of the involved random parameters
is not known exactly. In this talk, we study distributionally robust stochastic
programming (DRSP), in which the decision hedges against the worst possible
distribution that belongs to an ambiguity set. More specifically, we consider
the DRSP with the ambiguity set comprising all distributions that are close to some
reference distribution in terms of Wasserstein distance. We derive a tractable
reformulation of the DRSP problem by constructing the worst-case distribution
explicitly via the first-order optimality condition of the dual problem. Our
approach has several theoretical and computational implications. First, using
the precise characterization of the worst-case distribution, we show that the
DRSP can be approximated by robust programs to arbitrary accuracy, and thus
many DRSP problems become tractable with tools from robust optimization.
Second, when the objective is concave in the uncertainty, the robust-program
approximation is exact and equivalent to a saddle-point problem, which can be
solved by a Mirror-Prox algorithm. Third, our framework can also be applied to
problems other than stochastic programming, such as a class of distributionally
robust transportation problems. Furthermore, we perform sensitivity analysis
with respect to the radius of the Wasserstein ball, and apply our results to
the newsvendor problem, two-stage linear program with uncertainty-affected
recourse, and worst-case Value-at-risk analysis.

Series: ACO Student Seminar

I will give a tour of high-dimensional sampling algorithms, both from a theoretical and applied perspective, for generating random samples from a convex body. There are many well-studied random walks to choose from, with many of them having rigorous mixing bounds which say when the random walk has converged. We then show that the techniques from theory yield state-of-the-art algorithms in practice, where we analyze various organisms by randomly sampling their metabolic networks.This work is in collaboration with Ronan Fleming, Hulda Haraldsdottir ,and Santosh Vempala.

Series: ACO Student Seminar

We generalize the existing reduction mechanism due to Braun, Pokutta and Zink (2014)for linear programming problems and semidefinite programming problems in two ways 1) relaxing the requirement of affineness2) extending to fractional optimization problems As applications we prove several new LP-hardness and SDP-hardnessresults, e.g., for the (non-uniform) Sparsest Cut problem with bounded treewidth on the supply graph, the Balanced Separator problem with bounded treewidth onthe demand graph, the Max Cut problem and the Matching problem on 3-regular graphs.We also provide a new, very strong Lasserre integrality gapfor the Independent Set problem, which is strictly greater than thebest known LP approximation, showing that the Lasserre hierarchydoes not always provide the tightest SDP relaxation.Joint work with Gabor Braun and Sebastian Pokutta.

Series: ACO Student Seminar

We consider the Widom-Rowlinson model of two types of interacting particles on $d$-regular graphs. We prove a tight upper bound on the occupancy fraction: the expected fraction of vertices occupied by a particle under a random configuration from the model. The upper bound is achieved uniquely by unions of complete graphs on $d+1$ vertices. As a corollary we find that $K_{d+1}$ also maximizes the normalized partition function of the Widom-Rowlinson model over the class of $d$-regular graphs, proving a conjecture of Galvin. Joint work with Will Perkins and Prasad Tetali.

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.