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

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

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.

Series: ACO Student Seminar

Joint ARC colloquium/ACO student seminar

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.

Series: ACO Student Seminar

Given a family of ideals which are symmetric under some group action on the variables, a natural question to ask is whether the generating set stabilizes up to symmetry as the number of variables tends to infinity. We answer this in the affirmative for a broad class of toric ideals, settling several open questions coming from algebraic statistics. Our approach involves factoring an equivariant monomial map into a part for which we have an explicit degree bound of the kernel, and a part for which we canprove that the source, a so-called matching monoid, is equivariantly Noetherian. The proof is mostly combinatorial, making use of the theory of well-partial orders and its relationship to Noetherianity of monoid rings. Joint work with Jan Draisma, Rob Eggermont, and Anton Leykin.

Series: ACO Student Seminar

Database privacy has garnered a recent surge in interest from the theoretical science community following the seminal work of Dwork 2006, which proposed the strong notion of differential privacy. In this setting, each row of a database corresponds to the data owned by some (distinct) individual. An analyst submits a database query to a differentially private mechanism, which replies with a noisy answer guaranteeing privacy for the data owners and accuracy for the analyst. The mechanism's privacy parameter \epsilon is correlated negatively with privacy and positively with accuracy.This work builds a framework for creating and analyzing a market that 1) solves for some socially efficient value of \epsilon using the privacy and accuracy preferences of a heterogeneous body of data owners and a single analyst, 2) computes a noisy statistic on the database, and 3) collects and distributes payments for privacy that elicit truthful reporting of data owners' preferences. We present a market for database privacy in this new framework expanding on the public goods market of Groves and Ledyard, 1977.

Series: ACO Student Seminar

We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general membership oracle model. The complexity of the integration algorithm is O*(n^3) while the complexity of the sampling algorithm is O*(n^3) for the first sample and O*(n^2) for every subsequent sample. These bounds improve on the corresponding state-of-the-art by a factor of n. Our improvement comes from several aspects: better isoperimetry, smoother annealing, avoiding transformation to isotropic position and the use of the ``speedy walk" in the analysis.

Series: ACO Student Seminar

Since the 50s and Nash general proof of equilibrium existence in games it
is well understood
that even simple games may have many, even uncountably infinite, equilibria
with different properties.
In such cases a natural question arises, which equilibrium is the right one?
In this work, we perform average case analysis of evolutionary dynamics in
such cases of games.
Intuitively, we assign to each equilibrium a probability mass that is
proportional to the size of its
region of attraction. We develop new techniques to compute these
likelihoods for classic games
such as the Stag Hunt game (and generalizations) as well as balls-bins
games. Our proofs combine
techniques from information theory (relative entropy), dynamical systems
(center manifold theorem),
and algorithmic game theory.
Joint work with Georgios Piliouras

Series: ACO Student Seminar

First-order (a.k.a. subgradient) methods in convex optimization are a popular choice when facing extremely large-scale problems, where medium accuracy solutions suffice. The limits of performance of first-order methods can be partially understood under the lens of black box oracle complexity. In this talk I will present some of the limitations of worst-case black box oracle complexity, and I will show two recent extensions of the theory: First, we extend the notion of oracle compexity to the distributional setting, where complexity is measured as the worst average running time of (deterministic) algorithms against a distribution of instances. In this model, the distribution of instances is part of the input to the algorithm, and thus algorithms can potentially exploit this to accelerate their running time. However, we will show that for nonsmooth convex optimization distributional lower bounds coincide to worst-case complexity up to a constant factor, and thus all notions of complexity collapse; we can further extend these lower bounds to prove high running time with high probability (this is joint work with Sebastian Pokutta and Gabor Braun). Second, we extend the worst-case lower bounds for smooth convex optimization to non-Euclidean settings. Our construction mimics the classical proof for the nonsmooth case (based on piecewise-linear functions), but with a local smoothening of the instances. We establish a general lower bound for a wide class of finite dimensional Banach spaces, and then apply the results to \ell^p spaces, for p\in[2,\infty]. A further reduction will allow us to extend the lower bounds to p\in[1,2). As consequences, we prove the near-optimality of the Frank-Wolfe algorithm for the box and the spectral norm ball; and we prove near-optimality of function classes that contain the standard convex relaxation for the sparse recovery problem (this is joint work with Arkadi Nemirovski).

Series: ACO Student Seminar

In this talk, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on how both P and X are described, that is, on the encoding of the input data. For example, we analyze the case where the complete linear formulation of P is provided, as opposed to the case where P is given by an implicit description (to be defined in the talk). When P has binary vertices only, we provide additional tractability results and linear formulations of polynomial size. Some applications and extensions to integral polytopes will be discussed. Joint work with Shabbir Ahmed, Santanu S. Dey, and Volker Kaibel.

Series: ACO Student Seminar

Recently, Bilu and Linial formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor O(\sqrt{n})) perturbations, and subsequently Awasthi et al. considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations. In this talk, for center-based objectives, we present an algorithm that can optimally cluster instances resilient to (1+\sqrt{2})-factor perturbations, solving an open problem of Awasthi et al. For k-median, a center-based objective of special interest, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small fraction of the points after perturbation. We give the first bounds known for k-median under this more realistic and more general assumption. We also provide positive results for min-sum clustering which is a generally much harder objective than center-based objectives. Our algorithms are based on new linkage criteria that may be of independent interest.