[Colloquium] REMINDER! Talks at TTIC: Haris Angelidakis, TTIC Student

[Dawn Ellis]

When:     Friday, August 22nd at 11am

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room #526

Who:       Haris Angelidakis, TTIC Student

Title:       "Semidefinite Programming techniques for making non-binary
choices, and
              applications to Graph Partitioning Problems"

Abstract:

In this talk, we will look into some Semidefinite Programming Rounding
techniques and their applications in Graph Partitioning Problems. In
particular, we will present the notion of Orthogonal Separators, that was
introduced in a work of Chlamtac, Makarychev & Makarychev (2006), which
essentially serves as an embedding of an \ell_2^2 metric into \ell_1. We
will motivate the purpose of such an object by looking at the SDP of the
Unique Games problem, and we will show how it can be used as the main
component in rounding this SDP. As implied by its name, an Orthogonal
Separator tries to separate vectors that are orthogonal, or almost
orthogonal, in our \ell_2^2 metric. This property allows us to represent k
disjoint, non-binary, choices that the algorithm has to make (e.g. assign
one of k > 2 labels to every vertex of a graph while trying to minimize
some objective) as k pairwise orthogonal vectors in our SDP, and then round
the SDP solution by computing such an orthogonal separator, which will
ensure that we will only pick exactly one of the k disjoint vectors (and
so, our solution will be feasible).

We will then present an explicit construction of an Orthogonal Separator
(as appeared in Chlamtac et. al. 2006), and also generalize its definition
in order to make it a more flexible tool in the rounding of SDPs. Finally,
we will see some applications to Graph Partitioning problems, such as
k-Balanced Partitioning, Small Set Expansion, Sparsest k-Partitioning and
Non-Uniform Graph Partitioning, based on works of Krauthgamer, Naor &
Schwartz (2009), Bansal, Feige, Krauthgamer, Makarychev, Nagarajan, Naor &
Schwartz (2011), Louis & Makarychev (2014) and Makarychev & Makarychev
(2014).

Advisor:  Yury Makarychev,   yury at ttic.edu


-- 
*Dawn Ellis*
Administrative Coordinator,
Bookkeeper
773-834-1757
dellis at ttic.edu

TTIC
6045 S. Kenwood Ave.
Chicago, IL. 60637
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20140815/143e24b6/attachment.htm