The IBM Research/NYU/Columbia Theory Day

Friday, November 19, 2004
Room 109 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185


9:30 - 10:00 Coffee and bagels

10: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

Colloquium Information:

For directions, please see:

To subscribe to our mailing list, follow instructions at:


Yevgeniy Dodis
Baruch Shieber
Rocco Servedio


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

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 ( 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.

top | contact