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

Series: ACO Student Seminar

I present a new class of vertex cover and set cover games, with the price of anarchy bounds matching the best known
constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular
costs. In particular, the price of anarchy is 2 for vertex cover. The
basic intuition is that the members of the vertex cover form a Mafia
that has to "protect" the graph, and may ask ransoms from their
neighbors in exchange for the protection. These ransoms turn out to
capture a good dual solution to the linear programming relaxation. For linear costs we also exhibit
linear time best response dynamics that converge that mimic the classical greedy approximation algorithm of Bar-Yehuda
and Even. This is a joint work with Georgios Piliouras and Tomas Valla.

Series: ACO Student Seminar

Recently, there has been great interest in understanding the fundamental
limits of our ability to sample from the independent sets (i.s.) of a
graph. One approach involves the study of the so-called hardcore model,
in which each i.s. is selected with probability proportional to some fixed
activity $\lambda$ raised to the cardinality of the given i.s. It is
well-known that for any fixed degree $\Delta$, there exists a critical
activity $\lambda_{\Delta}$ s.t. for all activities below
$\lambda_{\Delta}$, the sampled i.s. enjoys a long-range independence
(a.k.a. uniqueness) property when implemented on graphs with maximum
degree $\Delta$, while for all activities above $\lambda_{\Delta}$, the
sampled i.s. exhibits long-range dependencies. Such phase transitions are
known to have deep connections to the inherent computational complexity of
the underlying combinatorial problems. In this talk, we study a family of
measures which generalizes the hardcore model by taking more structural
information into account, beyond just the number of nodes belonging to the
i.s., with the hope of further probing the fundamental limits of what we
can learn about the i.s. of a graph using only local information. In our
model, the probability assigned to a given i.s. depends not only on its
cardinality, but also on how many excluded nodes are adjacent to exactly
$k$ nodes belonging to the i.s., for each $k$, resulting in a parameter
for each $k$. We generalize the notion of critical activity to these
``neighborly measures", and give necessary and sufficient conditions for
long-range independence when certain parameters satisfy a
log-convexity(concavity) requirement. To better understand the phase
transitions in this richer model, we view the classical critical activity
as a particular point in the parameter space, and ask which directions can
one move and still maintain long-range independence. We show that the set
of all such ``directions of uniqueness” has a simple polyhedral
description, which we use to study how moving along these directions
changes the probabilities associated with the sampled i.s. We conclude by
discussing implications for choosing how to sample when trying to optimize
a linear function of the underlying probabilities.

Series: ACO Student Seminar

In this seminar, I will talk about a few recent developments in the random colorings, random weighted independent sets and other 2-spin
models on different classes of graphs such as the square lattices and the triangular free graphs. I will focus on the so-called spatial mixing property of these models and discuss about the consequences (e.g., fast mixing of the Markov chains) of the spatial mixing property
as well as the techniques of proving it.

Series: ACO Student Seminar

I will show a new approach based on the discrepancy of the constraint
matrix to verify integer feasibility of polytopes. I will then use this
method to show a threshold phenomenon for integer feasibility of random
polytopes.
The random polytope model that we consider is P(n,m,x0,R) - these are
polytopes in n-dimensional space specified by m "random" tangential
hyperplanes to a ball of radius R
centered around the point x0. We show
that there exist constants c_1 < c_2 such
that with high probability, the random polytope
P(n,m,x0=(0.5,...,0.5),R) is integer infeasible if R is less than
c_1sqrt(log(2m/n))
and the random polytope P(n,m,x0,R) is integer feasible for every center
x0 if the radius R is at least c_2sqrt(log(2m/n)). Thus, a
transition from infeasibility to feasibility happens within a constant
factor
increase in the radius. Moreover, if the polytope contains a ball
of radius Omega(log (2m/n)), then we can find an integer solution with
high probability (over the input) in randomized polynomial time.
This is joint work with Santosh Vempala.

Series: ACO Student Seminar

I will define planted distributions of random structures and give plenty of examples in different contexts: from balls and bins, to random permutations, to random graphs and CSP's. I will
give an idea of how they are used and why they are interesting. Then
I'll focus on one particular problem: under what conditions can you
distinguish a planted distribution from the standard distribution on a random structure and how can you do it?

Series: ACO Student Seminar

I'll give a high-level tour of how lattices are providing a powerful new mathematical foundation for cryptography. Lattices provide simple, fast, and highly parallel cryptoschemes that, in contrast with many of today's popular methods (like RSA and elliptic curves), even appear to remain secure against quantum computers.
No background in lattices, cryptography, or quantum computers will be
necessary -- you only need to know how to add and multiply vectors and
matrices.

Series: ACO Student Seminar

A fundamental result in the geometry of numbers states that any lattice free convex set in R^n has integer width bounded by a function of dimension, i.e. the so called Flatness Theorem for Convex Bodies. This result provides the theoretical basis for the polynomial solvability of Integer Programs with a fixed number of (general) integer variables. In this work, we provide a simplified proof of the Flatness Theorem with tighter constants. Our main technical contribution is a new tight bound on the smoothing parameter of a lattice, a concept developed within lattice based cryptography which enables comparisons between certain discrete distributions over integer points with associated continuous Gaussian distributions. Based on joint work with Kai-Min Chung, Feng Hao Liu, and Christopher Peikert.

Series: ACO Student Seminar

Abstract: A hitting set for a collection of sets T is a set that has a
non-empty intersection with eachset in T; the hitting set problem is
to find a hitting set of minimum cardinality. Motivated bythe fact
that there are instances of the hitting set problem where the number of
subsets to behit is large, we introduce the notion of implicit
hitting set problems. In an implicit hitting setproblem the
collection of sets to be hit is typically too large to list explicitly;
instead, an oracleis provided which, given a set H, either
determines that H is a hitting set or returns a set inT that H does
not hit. I will show a number of examples of classic implicit hitting
set problems,and give a generic algorithm for solving such problems
exactly in an online model.I will also show how this framework is
valuable in developing approximation algorithms by presenting
a simple on-line algorithm for the minimum feedback vertex set problem.
In particular, our algorithm
gives an approximation factor of 1+ 2 log(np)/(np) for the random graph
G_{n,p}.Joint work with Richard Karp, Erick Moreno-Centeno (UC, Berkeley) and Santosh Vempala (Georgia Tech).

Series: ACO Student Seminar

Billiards is a dynamical system generated by an uniform motion of a point particle (ray of light, sound, etc.) in a domain with piecewise smooth boundary. Upon reaching the boundary the particle reflected according to the law "the angle of incidence equals the angle of reflection". Billiards appear as natural models in various branches of physics. More recently this type of models were used in oceanography, operations research, computer science, etc. I'll explain on very simple examples what is a regular and what is chaotic dynamics, the mechanisms of chaos and natural measures of complexity in dynamical systems. The talk will be accessible to undergraduates.

Series: ACO Student Seminar

Local search is one of the oldest known optimization techniques. It has
been studied extensively by Newton, Euler, etc. It is known that this
technique gives the optimum solution if the function being optimized is
concave(maximization) or convex (minimization). However, in the general
case it may only produce a "locally optimum" solution. We study how to
use this technique for a class of facility location problems and give
the currently best known approximation guarantees for the problem and a
matching "locality gap".