DIMACS Workshop on Sublinear Algorithms

September 24 - 27, 2000
Nassau Inn, Princeton, New Jersey

Organizers:

Shafi Goldwasser, MIT, shafi@THEORY.LCS.MIT.EDU

Prabhakar Raghavan, Verity, pragh@verity.com

Ronitt Rubinfeld, NEC Research Institute, ronitt@research.nj.nec.com

Martin Strauss, AT&T Labs - Research, mstrauss@research.att.com

Workshop Program:

Sunday, September 24, 2000

12:00 - 1:00	Registration

1:00 - 1:15     Introduction and Greeting

1:15 - 2:15     Oded Goldreich, Weizmann Institute of Science
                An Introduction to Property Testing

2:45 - 3:15     Sofya Raskhodnikova, MIT
                Monotonicity Testing

3:15 - 4:00     Ravi Kumar, IBM Almaden Research Center
                Algebraic Property Testing

4:00 - 4:30     Break

4:30 - 5:00     Martin Strauss, AT&T Labs
                Secure Multiparty Computation of Approximations

5:00 - 5:30     Graham Cormode, Case Western Reserve University
                Short String Signatures

Monday September 25, 2000

8:30 - 9:30     Registration

9:30 - 10:15    Phil Gibbons, Bell Labs
                Synopsis Data Structures for Massive Data Sets

10:15 - 10:45   Sampath Kannan, University of Pennsylvania
                Spot Checkers

10:45 - 11:15   Break

11:15 - 11:45   Mahesh Viswanathan, DIMACS, Rutgers University
                Testing of Data Streams

11:45 - 12:15   Christian Sohler, Heinz Nixdorf Institut
                Soft Kinetic Data Structures

12:15 - 2:30    Lunch at the Nassau Inn

2:30 - 3:00     Jessica Fong, Princeton University
                An approximate L^P-Difference Algorithm for Msassive 
                Data Streams

3:00 - 3:45     Luca Trevisan, University of California - Berkeley
                Sublinear Time Error-Correction and Error-Detection

3:45 - 4:15     Break

4:15 - 5:00     Michael Krivelevich, Tel Aviv University
                Using the Regularity Lemma for Property Testing

5:00 - 5:30     Frederic Magniez, Universite Paris-Sud
                Multi-linearity Self Testing with Relative Error

5:30 - 6:00     Artur Czumaj, New Jersey Institute of Technology
                Property Testing in Computational Geometry

Tuesday September 26, 2000

8:30 - 9:30 Registration

9:30 - 10:15    Adam Buchsbaum, AT&T Labs
                External Memory Algorithms

10:15 - 10:45   Moni Naor, Weizmann Institute of Science
                Optimal Aggregation Algorithms for Middleware

10:45 - 11:15   Break

11:15 - 11:45   Benny Pinkas, STAR Lab, Intertrust Technologies
                Privacy Preserving Data Mining

11:45 - 12:15   Piotr Indyk, MIT
                Stable Distributions, Pseudorandom Generators, Embeddings and
                Data Stream Computation

12:15 - 2:00    Lunch Break

2:00 - 2:30     Silvio Micali, MIT
                Computationally Private Information Retrieval with
                Polylogarithmic Communication

2:30 - 3:00     Dana Ron, Tel Aviv University
                Testing of Clustering

3:15 - 3:45     Nina Mishra Fox, HP Labs
                Sublinear Approximate (PAC) Clustering

3:45 - 4:15     Sudipto Guha, Stanford University
                Clustering Data Streams

4:15 - 4:45     Break

4:45 - 5:15     Michael Bender, SUNY Stony Brook
                Cache-Oblivious Data Structures and Algorithms

5:15 - 5:45     Patrick White, Cornell University
                Testing that Distributions are Close with Applications
                to Markov Chains     
                

Wednesday September 27, 2000

8:30 - 9:30     Registration

9:30 - 10:00    Yuval Ishai, DIMACS and AT&T Labs
                Reducing the Servers' Computation in Private Information
                Retrieval: PIR with Preprocessing

10:00 - 10:30   Rafail Ostrovsky, Telcordia Technologies
                Dimension Reduction in the Hamming Cube and its
                Applications

10:30 - 11:00   Break

11:00 - 11:30   Tugkan Batu, Cornell University
                Fast Approximate PCP's for Multidimensional
                Bin-Packing Problems

11:30 - 12:00   William DuMouchel, AT&T Labs
                Data Squashing: Constructing Summary Data Sets

12:00 - 1:30    Lunch at the Nassau Inn

1:30 - 2:15     Ravi Kannan, Yale University
                Low Rank Approximations and Applications

2:15 - 2:45     Petros Drineas, Yale University
                Fast Monte-Carlo Algorithms for Matrix Multiplication

2:45 - 3:15     Break

3:15 - 3:45     Eldar Fischer, NEC Research Institute
                On the Strength of Comparisons in Property Testing

3:45 - 4:15     Yuval Rabani, Technion
                Agglomerative clustering in High Dimension

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage