Computer Science Colloquium

IBM Research/NYU/Columbia Theory Day

Various Speakers,

November 12, 2010 9:30AM
Warren Weaver Hall, 109
251 Mercer Street
New York, NY 10012

Fall 2010 Colloquia Calendar


New York University



9:30 - 10:00 Coffee and bagels

10:00 - 10:55 Prof. Boaz Barak
Subexponential Algorithms for Unique Games and
Related Problems

10:55 - 11:05 Short break

11:05 - 12:00 Dr. Matthew Andrews
Edge-Disjoint Paths via Raecke Decompositions

12:00 - 2:00 Lunch break

2:00 - 2:55 Prof. Ryan O'Donnell
Optimal Lower Bounds for Locality Sensitive Hashing
(except when q is tiny)

2:55 - 3:15 Coffee break

3:15 - 4:10 Prof. Toniann Pitassi
Pan Privacy and Differentially Private Communication

For directions, please see and (building 46)

To subscribe to our mailing list, follow instructions at

Yevgeniy Dodis
Tal Malkin
Tal Rabin
Baruch Schieber

Prof. Boaz Barak
(Microsoft Research and Princeton University)

Subexponential Algorithms for Unique Games and
Related Problems

We give subexponential time approximation algorithms for the unique
games and the small set expansion problems. Specifically, for some
absolute constant c, we give:

1. An exp(kn^epsilon)-time algorithm that, given as input a k-alphabet
unique game on n variables that has an assignment satisfying
1-epsilon^c fraction of its constraints, outputs an assignment
satisfying 1-epsilon fraction of the constraints.

2. An exp(n^epsilon/delta)-time algorithm that, given as input an
n-vertex regular graph that has a set S of delta n vertices with
edge expansion at most epsilon^c outputs a set S' of at most delta
n vertices with edge expansion at most epsilon.

We also obtain a subexponential algorithm with improved approximation
for the Multi-Cut problem, as well as subexponential algorithms with
improved approximations to Max-Cut, Sparsest-Cut and Vertex-Cover on
some interesting subclasses of instances.

Khot's Unique Games Conjecture (UGC) states that it is NP-hard to
achieve approximation guarantees such as ours for unique games. While
our results stop short of refuting the UGC, they do suggest that
Unique Games is significantly easier than NP-hard problems such as
3SAT, 3LIN, Label Cover and more, that are believed not to have a
subexponential algorithm achieving a non-trivial approximation ratio.

The main component in our algorithms is a new result on graph
decomposition that may have other applications. Namely we show that
for every delta>0 and a regular n-vertex graph G, by changing at most
delta fraction of G's edges, one can break G into disjoint parts so
that the induced graph on each part has at most n^epsilon eigenvalues
larger than 1-eta (where epsilon,eta depend polynomially on
delta). Our results are based on combining this decomposition with
previous algorithms for unique games on graphs with few large
eigenvalues (Kolla and Tulsiani 2007, Kolla 2010).

Joint work with Sanjeev Arora and David Steurer.


Dr. Matthew Andrews
(Bell Laboratories)

Edge-Disjoint Paths via Raecke Decompositions

The Edge-Disjoint Paths (EDP) problem is one of the original NP-hard
problems. We are given a set of source-destination pairs in a graph
and we wish to connect as many of them as possible using edge-disjoint

The Edge-Disjoint Paths with Congestion (EDPwC) problem is a
relaxation in which we want to route approximately as many demands as
in the optimum solution to EDP but we allow ourselves a small amount
of congestion on each edge.

In this talk we shall give a brief history of these problems and
describe a new algorithm for EDPwC based on the notion of a Raecke
decomposition. This algorithm gives a polylog(n) approximation for
the number of routed demands as long as we allow poly(log log n)
congestion on each edge.


Prof. Ryan O'Donnell
(Carnegie Mellon University and IAS)

Optimal Lower Bounds for Locality Sensitive Hashing
(except when q is tiny)

Locality Sensitive Hashing (LSH) is a widely used algorithmic tool,
combining hashing with geometry, with applications to nearest-neighbor
search. For points in {0,1}^d, one wants a family H of functions such
that if dist(x,y) <= r then Pr[h(x) = h(y)] >= p (when h is chosen randomly
from H), whereas if dist(x,y) >= cr then Pr[h(x) = h(y)] <= q.

For a fixed c, the quality of the LSH family is determined by the
smallness of its ``rho parameter'', namely rho = ln(1/p)/ln(1/q). In
their seminal 1998 work, Indyk and Motwani gave a simple LSH family
with rho <= 1/c. The only known lower bound, [Motwani-Naor-Panigrahy'07],
was that rho must be at least roughly 0.5/c.

In this work, we give a simple proof of the optimal lower bound,
rho >= 1/c. In one sentence, it follows from the fact that the
noise-stability of a boolean function at ``time'' t is a log-convex
function of t.

We will also discuss the fact that all results mentioned here rely
on the underpublicized assumption that q is not too small.

This is joint work with Yi Wu of IBM Research and Yuan Zhou of
Carnegie Mellon.


Prof. Toniann Pitassi
(University of Toronto)

Pan Privacy and Differentially Private
Communication Complexity

We study differential privacy in a distributed setting where two or
more parties would like to perform analysis of their joint data while
preserving privacy for all datasets. Our results imply almost tight
lower bounds on the accuracy of such data analyses, both for specific
natural functions (such as Hamming Distance) and in general. Our
bounds expose a sharp contrast between the two-party setting and the
simpler client-server setting (where privacy guarantees are
one-sided). In addition, our bounds demonstrate a dramatic gap between
the accuracy that can be obtained by differentially private data
analysis versus the accuracy attainable when privacy is relaxed to a
computational variant of differential privacy.

Our proof techniques expose connections between the ability to
approximate a function by a low-error differentially-private protocol
and the ability to approximate the function by a low-communication
protocol. Finally, our lower bounds have applications to pan private
algorithms. Loosely speaking, pan-private algorithms are streaming
algorithms where all stored data must be differentially private.

The work on pan-privacy is joint with: Cynthia Dwork, Moni Naor,
Guy Rothblum and Sergey Yekhanin. The work on differentially private
communication complexity is joint with: Andrew McGregor, Ilya Mironov,
Omer Reingold, Kunal Talwar and Salil Vadhan.

top | contact webmaster