New York Area Theory Day

Organized by: IBM/NYU/Columbia
Friday, November 12, 2010
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

The New York Area Theory Day is a semi-annual conference, aimed to bring together people in the New York Metropolitan area for one day of interaction and discussion.  The Theory Day features several (usually 4-5) hour-long presentations by leading theoretical computer scientists about state-of-the-art advances in various areas.  Some presentations give a survey of the latest advances in some area, while others may concentrate on a particular result.  
The meeting is free and open to everyone; in particular, students are encouraged to attend.

Program:

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 here and here (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 

==================================================================

Abstracts


                          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. 

==================================================================