Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 05291

Sublinear Algorithms

( Jul 17 – Jul 22, 2005 )

(Click in the middle of the image to enlarge)

Please use the following short url to reference this page:



The purpose of the Dagstuhl seminar ’Sublinear Algorithms’ was to bring together researchers working on the development of algorithms for very large data sets. Over the last few years data sets have become increasingly massive and the need to design special algorithms and data structures that deal with such amounts of data has emerged. For example, the set of all credit card transactions in the world for a month would have been considered a massive data set some time ago. That is comparable to the number of packet transactions a single router processes in one hour on an interface and we are now facing problems of analyzing the traffic at a large network of such routers, each with many interfaces! Internet traffic logs, clickstreams, web data are all examples of modern data sets that show unprecedented scale. Managing and analyzing such data sets forces us to revisit the traditional notions of efficient algorithms. The long-held golden standard of "linear algorithms" - algorithms that take time proportional to the input and store no more space than it takes to archive the input - is no longer as efficient as one needs or can afford. Thus, there is now a need for sublinear algorithms, that is algorithms that use resources (time and space) significantly less than the input size.

The main areas addressed in the workshop were property testing, sublinear time approximation algorithms, and data streaming algorithms. These areas are not only connected by the fact that they require algorithms with sublinear resources but also that they heavily rely on randomization and random sampling. Therefore, we hoped that this workshop helped to exchange ideas between these different areas.

During the seminar one could obtain a good overview of the current state of sublinear algorithms. In many interesting talks new algorithms and models as well as solutions to well-known open problems were presented.

Concluding remarks

The seminar was attended by 52 researchers from eight countries (19 USA, 13 Israel, 10 Germany, 4 Canada, 2 France, 2 United Kingdom, 1 Switzerland, 1 Hungary). From our own experience and the feedback from the participants we believe that the workshop was very successful. Interesting talks, fruitful discussions between researchers working on different areas of sublinear algorithms, and the wonderful working and living environment of Schloss Dagstuhl contributed to the success of the workshop.

  • Tugkan Batu (Simon Fraser University - Burnaby, CA)
  • Beate Bollig (Universität Frankfurt, DE) [dblp]
  • Bernard Chazelle (Princeton University, US) [dblp]
  • Graham Cormode (Bell Labs - Murray Hill, US) [dblp]
  • Artur Czumaj (NJIT - Newark, US) [dblp]
  • Michel de Rougemont (Université Paris Sud, FR)
  • Benjamin Doerr (Christian-Albrechts-Universität zu Kiel, DE) [dblp]
  • Petros Drineas (Rensselaer Polytechnic Institute - Troy, US)
  • Ayse Funda Ergun (Simon Fraser University - Burnaby, CA)
  • Eldar Fischer (Technion - Haifa, IL)
  • Gereon Frahling (Universität Paderborn, DE)
  • Katalin Friedl (Budapest University of Technology & Economics, HU) [dblp]
  • Oded Goldreich (Weizmann Institute - Rehovot, IL) [dblp]
  • Sudipto Guha (University of Pennsylvania - Philadelphia, US) [dblp]
  • Shirley Halevy (Technion - Haifa, IL)
  • Prahladh Harsha (Microsoft Corp. - Mountain View, US) [dblp]
  • Piotr Indyk (MIT - Cambridge, US) [dblp]
  • Sampath Kannan (University of Pennsylvania - Philadelphia, US) [dblp]
  • Marek Karpinski (Universität Bonn, DE) [dblp]
  • Tali Kaufman (Tel Aviv University, IL) [dblp]
  • Michael Krivelevich (Tel Aviv University, IL) [dblp]
  • Oded Lachish (University of Haifa, IL)
  • Christiane Lammersen (Universität Paderborn, DE)
  • Avner Magen (University of Toronto, CA)
  • Frédéric Magniez (Université Paris Sud, FR) [dblp]
  • Kevin Matulef (MIT - Cambridge, US)
  • Andrew McGregor (University of Pennsylvania - Philadelphia, US) [dblp]
  • Ulrich Carsten Meyer (MPI für Informatik - Saarbrücken, DE) [dblp]
  • Nina Mishra (Stanford University, US)
  • S. Muthu Muthukrishnan (Rutgers University - Piscataway, US) [dblp]
  • Alantha Newman (RWTH Aachen, DE) [dblp]
  • Ilan Newman (University of Haifa, IL) [dblp]
  • Mitsunori Ogihara (University of Rochester, US)
  • Michal Parnas (Academic College of Tel Aviv, IL)
  • Mike S. Paterson (University of Warwick - Coventry, GB) [dblp]
  • Rajeev Raman (University of Leicester, GB) [dblp]
  • Sofya Raskhodnikova (Weizmann Institute - Rehovot, IL)
  • Dana Ron (Tel Aviv University, IL)
  • Ronitt Rubinfeld (MIT - Cambridge, US) [dblp]
  • S. Cenk Sahinalp (Simon Fraser University - Burnaby, CA) [dblp]
  • Alex Samorodnitsky (The Hebrew University of Jerusalem, IL)
  • Miklos Santha (Université Paris Sud, FR) [dblp]
  • Martin Sauerhoff (TU Dortmund, DE)
  • Raimund Seidel (Universität des Saarlandes, DE) [dblp]
  • Rocco Servedio (Columbia University - New York, US) [dblp]
  • Asaf Shapira (Tel Aviv University, IL)
  • Adam Davison Smith (Weizmann Institute - Rehovot, IL) [dblp]
  • Christian Sohler (Universität Paderborn, DE) [dblp]
  • Angelika Steger (ETH Zürich, CH) [dblp]
  • Martin J. Strauss (University of Michigan - Ann Arbor, US)
  • Mario Szegedy (Rutgers University - Piscataway, US) [dblp]
  • Sergei Vassilvitskii (Stanford University, US) [dblp]
  • Suresh Venkatasubramanian (AT&T Labs Research - Florham Park, US) [dblp]

Related Seminars
  • Dagstuhl Seminar 08341: Sublinear Algorithms (2008-08-17 - 2008-08-22) (Details)