Project "Sublinear Time Algorithms"

[Members] [Support] [Overview] [Results]



Research supported by Deutsche Forschungsgemeinschaft, grants SO 514/3-1 and SO 514/3-2.


The development of efficient algorithms for analyzing large data sets has become a central topic in many applications of computer science: In many cases it is not even possible to completely store the input data of an algorithm completely on a hard disk due to its size, not to speak about storing it in the main memory for processing. In such cases, depending on environmental aspects, even linear time algorithms may be to slow for solving the problem efficiently enough. A feasible method for extracting relevant information out of the data may then be to work with random samples: Similarly to a survey, one tries to chose a sample cleverly to get a good representation of the overall data while on the other hand trying to minimize the sample size. Since an algorithm that uses this technique only looks at a small fraction of the data, we call such algorithms Sublinear Time Algorithms.
The aim of this project is the further development of techniques to for sublinear time algorithms. For this purpose, we concentrate on Property Testing and Sublinear Approximation Algorithms in sparse and geometric graphs for developing new algorithms for specific problems and new methods for the sampling procedure and its analysis; we will place particular emphasis on exemplary problems like Matching, Independent Sets, Vertex Cover or Travelling Salesperson. Additionally, we will try to find classes of problems for which one can give sublinear approximation algorithms.


Michal Adamaszek, Artur Czumaj and Christian Sohler: Testing Monotone Continuous Distributions on High-dimensional Real Cubes. In Proceedings of SODA 2010, pp. 56-65, 2010.

Tugkan Batu, Petra Berenbrink and Christian Sohler: A sublinear-time approximation scheme for bin packing. Theor. Comput. Sci. 410(47-49) pp. 5082-5092, 2009.

Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak and Christian Sohler: Planar Graphs: Random Walks and Bipartiteness Testing. In Proceedings of FOCS 2011, pp. 423-432, 2011.

Frank Hellweg, Melanie Schmidt and Christian Sohler: Testing Euclidean Spanners. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA), 2010.

Frank Hellweg and Christian Sohler: Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph Freeness. In Proceedings of the 20th Annual European Symposium on Algorithms (ESA), 2012.

Ilan Newman and Christian Sohler: Every property of hyperfinite graphs is testable. In Proceedings of STOC 2011, pp. 675-684, 2011.

Christian Sohler: Almost Optimal Canonical Property Testers for Satisfiability. In Proceedings of FOCS 2012, pp. 541-550, 2012.

Letzte Änderung am 11.03.2013 von F. Hellweg