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
(Directions)
Fall 2010 Colloquia Calendar
Host
New York University
Synopsis
Program
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
EdgeDisjoint 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
Complexity
For directions, please see http://www.cims.nyu.edu/direct.html and
http://cs.nyu.edu/csweb/Location/directions.html (building 46)
To subscribe to our mailing list, follow instructions at
http://www.cs.nyu.edu/mailman/listinfo/theoryny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
Tal Malkin tal@cs.columbia.edu
Tal Rabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com

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 kalphabet
unique game on n variables that has an assignment satisfying
1epsilon^c fraction of its constraints, outputs an assignment
satisfying 1epsilon fraction of the constraints.
2. An exp(n^epsilon/delta)time algorithm that, given as input an
nvertex 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 MultiCut problem, as well as subexponential algorithms with
improved approximations to MaxCut, SparsestCut and VertexCover on
some interesting subclasses of instances.
Khot's Unique Games Conjecture (UGC) states that it is NPhard 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 NPhard problems such as
3SAT, 3LIN, Label Cover and more, that are believed not to have a
subexponential algorithm achieving a nontrivial 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 nvertex 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 1eta (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)
EdgeDisjoint Paths via Raecke Decompositions
The EdgeDisjoint Paths (EDP) problem is one of the original NPhard
problems. We are given a set of sourcedestination pairs in a graph
and we wish to connect as many of them as possible using edgedisjoint
paths.
The EdgeDisjoint 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 nearestneighbor
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, [MotwaniNaorPanigrahy'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
noisestability of a boolean function at ``time'' t is a logconvex
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 twoparty setting and the
simpler clientserver setting (where privacy guarantees are
onesided). 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 lowerror differentiallyprivate protocol
and the ability to approximate the function by a lowcommunication
protocol. Finally, our lower bounds have applications to pan private
algorithms. Loosely speaking, panprivate algorithms are streaming
algorithms where all stored data must be differentially private.
The work on panprivacy 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.
