Project "Computational Geometric Learning"

[Members] [Support] [Overview] [Publications]


  • Prof. Dr. Christian Sohler
  • Christiane Lammersen


Research supported by the EU within the 7th Framework Programme under contract No. 255827.


High dimensional geometric data are ubiquitous in science and engineering, and thus processing and analyzing them is a core task in these disciplines. The proposed project aims at extending the success story of geometric algorithms with guarantees to high-dimensions. This is not a straightforward task. For many problems, no efficient algorithms exist that compute the exact solution in high dimensions. This behavior is commonly called the curse of dimensionality. We plan to address the curse of dimensionality by focusing on inherent structure in the data like sparsity or low intrinsic dimension, and by resorting to fast approximation algorithms. The following two kinds of approximation guarantees are particularly desirable: first, the solution approximates an objective better if more time and memory resources are employed (algorithmic guarantee), and second, the approximation gets better when the data become more dense and/or more accurate (learning theoretic guarantee). We want to follow an integrated approach of developing the foundations of a new field - computational geometric learning - theoretically, but also practically in the form of a high quality software library and application software.


Alexander Munteanu, Christian Sohler, Dan Feldman: Smallest enclosing ball for probabilistic data. In Proceedings of SOCG 2014, pp. 214-223, 2014.

Hendrik Fichtenberger, Melanie Schmidt: PROBI: A Heuristic for the probabilistic k-median problem. CoRR abs/1309.5781, 2013.

E. Ehsanfar, D. Feldman, C. Sohler: Orthogonal Range Clustering. CGL Technical Report No.: CGL-TR-73, 2013.

Christiane Lammersen, Melanie Schmidt, Christian Sohler: Probabilistic k-Median Clustering in Data Streams. In Proceedings of WAOA 2012, pp. 70-81, 2012.

Christian Sohler, David Woodruff: Subspace Embeddings for the L1-norm with Applications. In Proceedings of STOC 2011, pp. 755-764, 2011.