Colloquium Details
IBM Research/NYU/Columbia Theory Day
Speaker: Various Speakers
Location: Warren Weaver Hall 109
Date: November 12, 2010, 9:30 a.m.
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 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 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/theory-ny
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 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 paths.
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.
Notes:
In-person attendance only available to those with active NYU ID cards.