The Unique Games Conjecture, Integrality Gap for Cut Problems and the Embeddability of Negative Type Metrics into L_1
It has been a long standing conjecture that negative type metrics (metrics
that are squares of Euclidean metrics) embed into L_1 with constant
distortion. Negative type metrics arise naturally as solutions of
semidefinite relaxations for Sparsest Cut and other Graph Partitioning
problems. This folklore conjecture implies that the "integrality ratio"
for the SDP-relaxation is bounded by a constant (which in turn gives a
constant factor approximation algorithm for Sparsest Cut). The recent
breakthrough algorithm of [Arora Rao Vazirani] gave O(\sqrt{log n}) upper
bound on the integrality ratio and they conjectured a constant upper
bound.
We disprove both of the above conjectures by constructing an integrality
ratio example with ratio (loglog n)^{1/4}. Surprisingly, our construction
is inspired from complexity theoretic tools: PCPs, Fourier Analysis, and
the Unique Games Conjecture (UGC) by [Khot]. The techniques have no a
priori connection with metric embeddings!
In this (self-contained) talk, I will give a overview of our construction.
This is joint work with Subhash Khot of Georgia Tech.
Monte-Carlo Algorithms for Matrices and Massive Datasets
We are interested in developing and analyzing fast Monte Carlo algorithms
for performing useful computations on large matrices, and their applications
to massive datasets. Examples of such computations include matrix
multiplication, the computation of the Singular Value Decomposition of a
matrix, the computation of CUR type decompositions of matrices, and testing
the feasibility or infeasibility of a linear program. We present a
Pass-Efficient model of data streaming computation in which our algorithms
may naturally be formulated and present algorithms that are efficient within
this model for each of the four types of matrix operations mentioned
previously. We also discuss various applications of these methods to the
analysis of massive data sets.
This is joint work with Ravi Kannan and Michael Mahoney.
Approximating matrices, tensors by random
sub-structures and Algorithmic applications
The talk will discuss randomized algorithms for finding low-rank
approximations to matrices. One typical result says that we can
approximate any matrix given just a small random subset of rows and a
random subset of columns [for a careful choice of sampling
probabilities], where the error is measured in the standard norms.
Besides traditional numerical applications, we discuss many
combinatorial applications of low-rank approximations. For graph
problems, one deals with the adjacency matrix. Similar techniques can
be used also for Boolean Satisfiability and other Constraint
satisfaction problems, where instead of matrices, we have tensors in
general.
Approximating separators using single commodity flows
Partitioning a graph into two large pieces while minimizing the size of
the "interface" between them is a fundamental combinatorial problem. We
show that such separators can be approximated within a polylogarithmic
factor in time O*(n^{3/2}) using single commodity max-flows. Previous
algorithms are based on multi-commodity flows which take time
O*(n^2). Our algorithm iteratively employs eigenvector and max-flow
computations to embed an expander flow, thus providing a certificate of
expansion. We use as a subroutine a balanced cut procedure of Spielman
and Teng.
This is joint work with Satish Rao and Umesh Vazirani.
An Unconditional Study of Computational Zero Knowledge
We prove a number of general theorems about ZK, the class of
problems possessing computational zero-knowledge proofs.
Our results are *unconditional*, in contrast to most previous
works on ZK, which rely on the assumption that one-way functions
exist.
In particular, we show that:
Optimization and Algorithms: New approaches and proofs of conjectures
The area of optimization seeks, broadly, to minimize a cost function
subject to constraints on the solution set. More concretely, it also
concerns the design of efficient algorithms for finding optimal or
near-optimal solutions. Over the past few years new approaches from Spin
Glass Theory, a branch of statistical physics, have been used to propose
solutions and efficient algorithms for hard optimization problems in
Electrical Engineering and Computer Science.
This talk will overview this interplay and focus on two examples:
(i) The Random Assignment Problem (RAP), which arises in a variety
of practical scenarios; notably in crossbar switch scheduling.
(ii) The Number Partitioning Problem (NPP), which models load balancing
and multiprocessor scheduling. I will trace the history of these problems
and state some conjectures regarding the cost and the structure of the
optimal solutions obtained by the powerful (but non-rigorous) methods
of physics. I will then sketch our resolution of the Parisi and
Coppersmith-Sorkin Conjectures for the RAP, and of the local Random
Energy Model Conjecture for the NPP. Finally, I will explain how
the methods of physics have yielded remarkably efficient algorithms
for turbo codes, image reconstruction, constraint satisfaction, and
other problems.
Graph Partitioning, Clustering with Qualitative Information, and Grothendieck-type Inequalities
In this talk we will describe applications of Grothendieck's inequality to
combinatorial optimization. We will show how Grothendieck's inequality can
be used to provide efficient algorithms which approximate the cut-norm of
a matrix, and construct Szemeredi partitions. Moreover, we will show how
to derive a new class of Grothendieck type inequalities which can be used
to give approximation algorithms for Correlation Clustering on a wide
class of judgment graphs, and approximate ground states of spin glasses.
No prerequisites will be assumed, in particular, we will present a proof
of Grothendieck's inequality.
Based on joint works with N. Alon, K. Makarychev and Y. Makarychev.
On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
Our main result is a reduction from worst-case lattice problems such as
SVP and SIVP to a certain learning problem. This learning problem is a
natural extension of the `learning from parity with error' problem to
higher moduli. It can also be viewed as the problem of decoding from a
random linear code. This, we believe, gives a strong indication that
these problems are hard. Our reduction, however, is quantum. Hence, an
efficient solution to the learning problem implies a _quantum_ algorithm
for SVP and SIVP. A main open question is whether this reduction can be
made classical.
Using the main result, we obtain a public-key cryptosystem whose
hardness is based on the worst-case quantum hardness of SVP and
SIVP. Previous lattice-based public-key cryptosystems such as the one by
Ajtai and Dwork were only based on unique-SVP, a special case of
SVP. The new cryptosystem is much more efficient than previous
cryptosystems: the public key is of size \tilde{O}(n) and encrypting a
message increases its size by \tilde{O}(n) (in previous cryptosystems
these values are \tilde{O}(n^4) and \tilde{O}(n^2), respectively).
Spectral Projection and Single Linkage:
Learning Concentrated Distributions the Easy Way
We look at the problem of clustering data points that have been drawn
from a mixture of concentrated distributions (each sample is drawn from
one of k different concentrated distributions). After surveying some
previous work on classifying samples from Gaussian mixtures, we
consider a very simple algorithm based on the combination of spectral
projection (via the singular value decomposition) and single linkage
clustering (partitioning by cutting the heaviest edge in a MST). These
two pieces fit together to give a simple, efficient algorithm with a
concise analysis that outperforms all previous approaches. We also give
a short lower bound demonstrating that the algorithm's performance is
tight, up to a term that depends on the concentration properties of the
distribution.
Online conflict free coloring
We consider an online version of the conflict-free coloring
problem. In one dimension we are given a sequence of points on the
line. Each newly inserted point must be assigned a color upon
insertion, and at all times the coloring has to be {\em
conflict-free}, in the sense that in every interval $I$ there is a
color that appears exactly once. The goal is to minimize the
number of colors used.
We present several deterministic and randomized algorithms for
achieving this goal, and bound the number of colors they use. If time
allows I will also talk about more recent results for analogous
problems in the plane.
Joint work with Amos Fiat, Meital Levy, Jiri Matousek, Elchanan
Mossel, Janos Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo
Welzl.
Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and (Local) Treewidth
Our newly developing theory of bidimensional graph problems provides
general techniques for designing efficient fixed-parameter algorithms and
approximation algorithms for NP-hard graph problems in broad classes of
graphs. This theory applies to graph problems that are
\emph{bidimensional} in the sense that (1) the solution value for the $k
\times k$ grid graph (and similar graphs) grows with $k$, typically as
$\Omega(k^2)$, and (2) the solution value goes down when contracting edges
and optionally when deleting edges. Examples of such problems include
feedback vertex set, vertex cover, minimum maximal matching, face cover, a
series of vertex-removal parameters, dominating set, edge dominating set,
$r$-dominating set, connected dominating set, connected edge dominating
set, connected $r$-dominating set, and unweighted TSP tour (a walk in the
graph visiting all vertices). Bidimensional problems have many structural
properties; for example, any graph embeddable in a surface of bounded
genus has treewidth bounded above by the square root of the problem's
solution value. These properties lead to efficient---often
subexponential---fixed-parameter algorithms, as well as polynomial-time
approximation schemes, for many minor-closed graph classes. One type of
minor-closed graph class of particular relevance has bounded local
treewidth, in the sense that the treewidth of a graph is bounded above in
terms of the diameter; indeed, we show that such a bound is always at most
linear. The bidimensionality theory unifies and improves several previous
results. The theory is based on algorithmic and combinatorial extensions
to parts of the Robertson-Seymour Graph Minor Theory, in particular
initiating a parallel theory of graph contractions. The foundation of this
work is the topological theory of drawings of graphs on surfaces.
This is from several joint papers mainly with Erik D. Demaine.
Euclidean distortion and the Sparsest Cut
Two of the fundamental problems in the field of discrete metric spaces
concern embedding metrics of negative type into L_1, and embedding finite
subsets of L_1 into a Euclidean space. The former problem has come to
prominence because of its intimate relationship with computing the
Sparsest Cut in graphs, and the latter because of its role in the local
theory of Banach spaces. In this talk, I will present recent progress on
both questions. In particular, I will show that every n-point metric of
negative type has Euclidean distortion which is bounded above by
sqrt{log n log log n}, a result which is optimal up to the log log n
factor. This leads immediately to an
O(sqrt{log n log log n})-approximation for the Sparsest Cut problem with
general demands.
This is joint work with Sanjeev Arora and Assaf Naor.