skip to content

Center for Data and Simulation Science

Christian Sohler and his group study algorithmic foundations of the analysis of very large data sets. In the area of sublinear time algorithms they investigate how to get information about the structure of very large graphs with random sampling. In data streaming the objective is to design algorithms that process the input data sequentially and with much less space than required to store the whole input. The research group is particularly interested in sublinear time and streaming algorithms for clustering problems on very large data sets.

Selected publications

  1. S. Lattenzi and C. Sohler. A better k-means++ algorithm via local search. Proceedings of the 36th International Conference on Machine Learning (ICML), p. 3662-3671, 2019.
  2. C. Sohler and D. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), p. 802-813, 2018.
  3. L. Geppert, K. Ickstadt, A. Munteanu, J. Quedenfeld, C. Sohler. Random projections for Bayesian regression. Statistics and Computing 27(1): 79-101, 2017.
  4. A. Czumaj, P. Peng, and C. Sohler. Testing cluster structure of graphs. Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), p. 723-732, 2015.
  5. D. Cohen-Steiner, W. Kong, C. Sohler, and G. Valiant. Approximating the spectrum of a graph. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), p. 1263-1271, 2018.
  6. I. Newman and C. Sohler. Every property of hyperfinte graphs is testable. SIAM Journal on Computing, 42(3): 1095-1112, 2013.
  7. M. Ackermann, M. Märtens, C. Raupack, K. Swierkot, C. Lammersen, and C. Sohler. StreamKM++: A clustering algorithm for data streams. ACM Journal of Experimental Algorithmics, 17(1), 2012.
  8. M. Ackermann, J. Blömer, and C. Sohler. Clustering for metric and nonmetric distance measures. ACM Transactions on Algorithms 6(4): 59:1-59:26, 2010.
  9. A. Czumaj, A. Shapira, and C Sohler. Testing hereditary properties of nonexpanding bounded-degree graphs. SIAM Journal on Computing 39(6): 2499-2510, 2009
  10. A. Czumaj, C. Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM Journal on Computing 39(3): 904-922, 2009.