DIMACS Workshop on Sublinear Algorithms

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

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
Presented under the auspices of the Special Year on Massive Data Sets, the Special year on Computational Intractability and
Exploratory Workshops/Special Programs.

Recent advances in computing power and the trend toward interconnecting computers has resulted in a tremendous increase in the size of datasets that are gathered and considered useful. Such data sets come from a wide variety of sources; for example they might contain information describing the structure or content of the world wide web, Internet traffic flow, traffic and clickstream patterns of individuals or large groups of users, warehoused operational data from enterprises, or ongoing measurements of scientific observations.

The unprecedented scale of these data sets demands that we revisit traditonal notions of efficient algorithms. In many applications, this means that the computational resources used be small relative to the size of the data. Because of the severity of the constraints, one might think that there is only hope for solving problems that can be solved by straightforward statistical sampling techniques.

Surprisingly, researchers in several different areas of mathematics and computer science have recently shown that interesting results can be obtained under such sublinear constraints. Besides techniques from sampling, many of these results incorporate sophisticated algorithmic and combinatorial contributions to solve appropriate approximate variations of the problems. To study this emerging area, we propose to bring together researchers working in several communities, including combinatorial property testing, streaming algorithms, randomized algorithms and learning theory. Many of the researchers in these different areas have had experience with massive data sets that occur in diverse domains such as the web and databases; by bringing these people together, we hope to advance participants' research by establishing common issues.

Limited support might be available, please contact either Ronitt Rubinfeld, ronitt@research.nj.nec.com or Martin Strauss, mstrauss@research.att.com.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 12, 2000.