The IBM Research | NYU | Columbia THEORY DAY Friday, November 19, 2004

New York University, Courant Institute Room 109 Warren Weaver Hall251 Mercer Street New York, NY 10012

The IBM Research | NYU | Columbia 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
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:

 9:30  - 10:00   Coffee and bagels10:00  - 10:55   Prof. Sampath Kannan		 Algorithms for Streamed Graphs and Streaming Lower Bounds 10:55  - 11:05   Short break 11:05  - 12:00   Prof. Sanjeev Arora 		 Geometric Embeddings, Graph Partitioning, and Expander Flows:  A Survey of Recent Results                  12:00  -  2:00   Lunch break 2:00  -  2:55   Prof. Silvio Micali                  Collusion Free Protocols 2:55  -  3:15   Coffee break 3:15  -  4:10   Prof. Joan Feigenbaum                 Progress on the PORTIA Project

The Theory Day will be held at Room 109 Warren Weaver Hall,Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012Click here or here for directions. To subscribe to our mailing list, follow instructions here.

Organizers:

Yevgeniy Dodis (NYU)

Tal Rabin (IBM Research)

Baruch Schieber (IBM Research)

Rocco Servedio (Columbia)

Abstracts:

	     Algorithms and Lower Bounds for Streamed Graphs
Prof. Sampath Kannan                    (University of Pennsylvania)

The streaming model of computation is relevant to situations where the
amount of input data far exceeds the storage capacity of the computer.
The model typically assumes that the space available is polylogarithmic in
the size of the input and that the input is streamed in a read once fashion.

In this talk we consider the situation where the input is a graph with n
vertices and m edges, whose edges are streamed (in adversarial order).
After arguing that o(n) space is insufficient even for the simplest''
tasks, we focus on what can be done with space O(n polylog n). Here too
the news is not very good when we restrict our attention to one-pass
algorithms. After showing some one pass algorithms for approximating the
distance, approximating the size and weight of matchings etc., we turn
our attention to multipass algorithms. We show pass-space trade-offs for
matching and lower bounds for a pointer-chasing-like problem.

Joint work with Joan Feigenbaum, Andrew McGregor, Siddharth Suri, Jian
Zhang.
Geometric Embeddings, Graph Partitioning, and Expander Flows:                        A Survey of Recent Results                                                                                                           Prof. Sanjeev Arora                          (Princeton University)

Partitioning a graph into two (or more) large pieces while minimizing the
size of the interface'' between them is a fundamental combinatorial
problem. Graph partitions or separators are central objects of study in
the theory of Markov chains, geometric embeddings and are a natural
algorithmic primitive in numerous settings, including clustering, divide
and conquer approaches, PRAM emulation, VLSI layout, and packet routing
in distributed networks. Most versions of graph partitioning are NP-hard,
so researchers have tried to develop approximation algorithms.

The past year has seen a flurry of new approximation algorithms, starting
with a paper of mine with Satish Rao and Umesh Vazirani in STOC'04 that
gave a \sqrt{log n}-approximation for SPARSEST CUT. This improved
classical algorithms based upon both spectral methods and multicommodity
flows (Leighton Rao 1988; O(log n)-approximation).  We also introduced
the notion of expander flows, which constitute an interesting
certificate'' of a graph's expansion.

The [ARV] algorithm used semidefinite programming and hence was not too
efficient. In joint work with Hazan and Kale (FOCS'04) we give a more
combinatorial algorithm. It runs in near-quadratic time, raising hopes of
practical impact.

Finally, the ideas used in the [ARV] approximation algorithm have led to
sudden progress in another research area: low-distortion embeddings of
finite metric spaces into geometric spaces (such as l_2). Recent
unpublished papers (Chawla, Gupta, Racke; improved upon in my joint work
with Lee and Naor) show how to embed n-point subsets of l_1 into l_2 with
distortion much better than Bourgain's bound of O(log n) from 1985. Thus
algorithmic ideas have helped resolve questions in pure mathematics.

The talk will be a self-contained survey of the above results, as well as
several papers not mentioned above.
Collusion Free Protocols
Prof. Silvio Micali                                     (MIT)

Secure computation does not prevent a set of bad players from sharing
information and coordinating their actions during a protocol.  But not
even two colluding players should be tolerated in ---say--- Mental Poker.

We define Collusion-Free Protocols, and construct them (under standard
physical and computational assumptions) for Poker, Bridge and all similar
games.

A key step of our solution is making steganography provably impossible.

Joint work with Matt Lepinski and Abhi Shelat.

Progress on the PORTIA Project
Prof. Joan Feigenbaum                            (Yale University)

Increasing use of computers and networks in business, government,
recreation, and almost all aspects of daily life has led to a
proliferation of online sensitive data, i.e., data that, if used
improperly, can harm the data subjects, data owners, data users, or other
relevant parties.  As a result, concern about the ownership, control,
privacy, and accuracy of these data has become a top priority. PORTIA
(http://crypto.stanford.edu/portia/) is a large-ITR project focused on
both the technical challenges of handling sensitive data and the policy
and legal issues facing data subjects, data owners, and data users.  The
project has been in operation since Oct 2003.  This talk, suitable both
for a Computer Science audience and for a "Society and Technology"
audience, will survey some of the progress and some of the remaining open
questions in the PORTIA project.

http://www.cs.yale.edu/homes/jf


"Every day is Theory Day"