The IBM Research/NYU/Columbia Theory Day
Friday, April 28, 2006
Davis auditorium
Columbia University
412 Schapiro (CEPSR) Building
New York, NY
Program
9:30  10:00 Coffee and bagels
10:00  10:55 Prof. Bernard Chazelle (Princeton University)
DataDriven Algorithm Design
10:55  11:05 Short Break
11:05  12:00 Michael Saks (Rutgers University)
A Lower Bound for Cooperative Broadcast in the Presence of Noises
12:00  2:00 Lunch break
2:00  2:55 Prof. Subhash Khot (Georgia Institute of Technology)
Lower Bounds for Approximating MAXCUT and Sparsest Cut
2:55  3:15 Coffee break
3:15  4:10 Dr. Corinna Cortes (Google Labs)
The Next Algorithmic and Theoretical Challenges for Search Engines
For directions, please see: http://www.cs.columbia.edu/theory/directions.html
To subscribe to our mailing list, follow instructions at: http://www.cs.nyu.edu/mailman/listinfo/theoryny
Organizers:
Yevgeniy Dodis dodis@cs.nyu.edu
TalRabin talr@watson.ibm.com
Tal Malkin tal@cs.columbia.edu
Baruch Schieber sbar@watson.ibm.com
The organizers also thank Google Labs for their generous support.
Abstracts
DataDriven Algorithm Design
Prof. Bernard Chazelle
Princeton University
Motivated by the need to cope with data that is massive,
highdimensional, noisy, uncertain, unevenly priced, lowentropic, or
all of the above, algorithm design is undergoing profound changes.
I will discuss some of these developments; in particular,
sublinear algorithms, online reconstruction, selfimproving
algorithms, and dimension reduction.
A Lower Bound for Cooperative Broadcast in the Presence of Noise
Prof. Michael Saks
Rutgers University
In a noisy broadcast channel, processors communicate as follows:
in each time step, one processor broadcasts a bit. Each of the
other processors receives a bit, but the received bit is incorrect
with some known probability p. Reception errors are assumed to be
independent. In such an environment, a group of n broadcasters, each
possessing a bit, wish to transmit all n bits to a receiver so that,
with probability close to 1, the receiver learns all of the bits
correctly. This can be done easily with O(n log n) broadcasts, by
having each processor broadcast its input bit C log n times (for some
sufficiently large constant C) and having the receiver decode each bit
by majority vote. This naive algorithm was improved by Gallager who, in
1988,gave an algorithm that uses only O(n log log n) broadcasts. I'll
describe a recent result, obtained with Navin Goyal and Guy Kindler, showing that
Gallager's algorithm is optimal up to a constant factor.
Lower Bounds for Approximating MAXCUT and Sparsest Cut
Prof. Subhash Khot
Georgia Institute of Technology
Goemans and Williamson, in their seminal 1994 paper, introduced the
use of semidefinite programming as an algorithmic tool. Using a
natural SDPrelaxation and a rounding procedure, they obtained 0.878..
approximation to MAXCUT problem. Since then, the technique has found
several applications including the recent breakthrough result of
Arora, Rao and Vazirani that gave O(sqrt{log n}) approximation to the
Sparsest Cut problem.
I will talk about recent results proving lower bounds on the appr
oximatbility of MAXCUT and Sparsest Cut. These lower bounds are of
two types: firstly, hardness of approximation results assuming the
Unique Games Conjecture and secondly, unconditional and explicit
intergrality gaps for the SDP relaxations (even with socalled
triangle inequality constraints). The lower bound for MAXCUT matches
exactly with the Goemans Williamson's bound. The integrality gap
result for Sparsest Cut disproves a conjecture of Goemans and Linial
that the negative type metrics embed into L_1 with constant
distortion.
Based on joint works with [Guy Kindler, Elchanan Mossel and Ryan
O'donnell], [Nisheeth Vishnoi] and [Nikhil Devanur, Rishi Saket and
Nisheeth Vishnoi].
The Next Algorithmic and Theoretical Challenges for Search Engines
Dr. Corinna Cortes
Google Labs
Search engines have been around for more than a decade. Some of the
problems that seemed at first intractable have found common practical
solutions. But much is still left to organize the information in the
world. What are the next challenges faced by search engines? How can
search be further improved? This talk presents and discusses several
algorithmic and theoretical problems that arise in this context of the
design of search engines.
top  contact webmaster@cs.nyu.edu
