Christian Sohler

According to our database, Christian Sohler authored at least 115 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Sublinear Time Approximation of the Cost of a Metric \({k}\)-Nearest Neighbor Graph.

Artur Czumaj, Christian Sohler

SIAM J. Comput., 2024

On the adversarial robustness of Locality-Sensitive Hashing in Hamming space.

Michael Kapralov, Mikhail Makarov, Christian Sohler

CoRR, 2024

2022

Constant Approximation for Normalized Modularity and Associations Clustering.

Jakub Lacki, Vahab Mirrokni, Christian Sohler

CoRR, 2022

Motif Cut Sparsifiers.

Michael Kapralov, Mikhail Makarov, Sandeep Silwal, Christian Sohler, Jakab Tardos

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

A Sublinear Local Access Implementation for the Chinese Restaurant Process.

Peter Mörters, Christian Sohler, Stefan Walzer

Proceedings of the Approximation, 2022

2021

Spectral Clustering Oracles in Sublinear Time.

Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, Christian Sohler

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Parallel and Efficient Hierarchical k-Median Clustering.

Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

Turning Big Data Into Tiny Data: Constant-Size Coresets for k-Means, PCA, and Projective Clustering.

Dan Feldman, Melanie Schmidt, Christian Sohler

SIAM J. Comput., 2020

Streaming statistical models via Merge & Reduce.

Leo N. Geppert, Katja Ickstadt, Alexander Munteanu, Christian Sohler

Int. J. Data Sci. Anal., 2020

Sublinear time approximation of the cost of a metric <i>k</i>-nearest neighbor graph.

Artur Czumaj, Christian Sohler

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Fast and Accurate $k$-means++ via Rejection Sampling.

Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, Ola Svensson

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Testable Properties in General Graphs and Random Order Streaming.

Artur Czumaj, Hendrik Fichtenberger, Pan Peng, Christian Sohler

Proceedings of the Approximation, 2020

2019

Testing for forbidden order patterns in an array.

Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler

Random Struct. Algorithms, 2019

Planar graphs: Random walks and bipartiteness testing.

Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, Christian Sohler

Random Struct. Algorithms, 2019

A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs).

Artur Czumaj, Christian Sohler

CoRR, 2019

Fully dynamic hierarchical diameter k-clustering and k-center.

Melanie Schmidt, Christian Sohler

CoRR, 2019

Fair Coresets and Streaming Algorithms for Fair k-means.

Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler

Proceedings of the Approximation and Online Algorithms - 17th International Workshop, 2019

Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty.

Hendrik Fichtenberger, Pan Peng, Christian Sohler

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Better k-means++ Algorithm via Local Search.

Silvio Lattanzi, Christian Sohler

Proceedings of the 36th International Conference on Machine Learning, 2019

A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs).

Artur Czumaj, Christian Sohler

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Dissection-BKW.

Andre Esser, Felix Heuer, Robert Kübler, Alexander May, Christian Sohler

IACR Cryptol. ePrint Arch., 2018

Fair Coresets and Streaming Algorithms for Fair k-Means Clustering.

Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler

CoRR, 2018

Estimating Graph Parameters from Random Order Streams.

Pan Peng, Christian Sohler

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On Coresets for Logistic Regression.

Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Approximating the Spectrum of a Graph.

David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant

Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018

A Property Testing Framework for the Theoretical Expressivity of Graph Kernels.

Nils M. Kriege, Christopher Morris, Anja Rey, Christian Sohler

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension.

Christian Sohler, David P. Woodruff

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Sublinear Clustering.

Artur Czumaj, Christian Sohler

Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Random projections for Bayesian regression.

Leo N. Geppert, Katja Ickstadt, Alexander Munteanu, Jens Quedenfeld, Christian Sohler

Stat. Comput., 2017

Clustering High Dimensional Dynamic Data Streams.

Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, Lin F. Yang

Proceedings of the 34th International Conference on Machine Learning, 2017

Testable Bounded Degree Graph Properties Are Random Order Streamable.

Morteza Monemizadeh, S. Muthukrishnan, Pan Peng, Christian Sohler

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Distributed Monitoring of Network Properties: The Power of Hybrid Networks.

Robert Gmyr, Kristian Hinnenthal, Christian Scheideler, Christian Sohler

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Theoretical Analysis of the k-Means Algorithm - A Survey.

Johannes Blömer, Christiane Lammersen, Melanie Schmidt, Christian Sohler

Proceedings of the Algorithm Engineering - Selected Results and Surveys, 2016

Theoretical Analysis of the $k$-Means Algorithm - A Survey.

Johannes Blömer, Christiane Lammersen, Melanie Schmidt, Christian Sohler

CoRR, 2016

Relating two property testing models for bounded degree directed graphs.

Artur Czumaj, Pan Peng, Christian Sohler

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Clustering time series under the Fréchet distance.

Anne Driemel, Amer Krivosija, Christian Sohler

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Diameter and k-Center in Sliding Windows.

Vincent Cohen-Addad, Chris Schwiegelshohn, Christian Sohler

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Probabilistic k-Median Clustering in Data Streams.

Christiane Lammersen, Melanie Schmidt, Christian Sohler

Theory Comput. Syst., 2015

Testing Cluster Structure of Graphs.

Artur Czumaj, Pan Peng, Christian Sohler

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

On Constant-Size Graphs That Preserve the Local Structure of High-Girth Graphs.

Hendrik Fichtenberger, Pan Peng, Christian Sohler

Proceedings of the Approximation, 2015

2014

Asymptotically exact streaming algorithms.

Marc Heinrich, Alexander Munteanu, Christian Sohler

CoRR, 2014

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem.

Joachim Gehweiler, Christiane Lammersen, Christian Sohler

Algorithmica, 2014

Analysis of Agglomerative Clustering.

Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, Christian Sohler

Algorithmica, 2014

What Does the Local Structure of a Planar Graph Tell Us About Its Global Structure?

Christian Sohler

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Signal/Background Classification of Time Series for Biological Virus Detection.

Dominic Siedhoff, Hendrik Fichtenberger, Pascal Libuschewski, Frank Weichert, Christian Sohler, Heinrich Müller

Proceedings of the Pattern Recognition - 36th German Conference, 2014

Smallest enclosing ball for probabilistic data.

Alexander Munteanu, Christian Sohler, Dan Feldman

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013

Every Property of Hyperfinite Graphs Is Testable.

Ilan Newman, Christian Sohler

SIAM J. Comput., 2013

Property-Testing in Sparse Directed Graphs: 3-Star-Freeness and Connectivity.

Frank Hellweg, Christian Sohler

CoRR, 2013

Turning big data into tiny data: Constant-size coresets for <i>k</i>-means, PCA and projective clustering.

Dan Feldman, Melanie Schmidt, Christian Sohler

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

(1+ Є)-approximation for facility location in data streams.

Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, Christian Sohler

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

BICO: BIRCH Meets Coresets for k-Means Clustering.

Hendrik Fichtenberger, Marc Gillé, Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler

Proceedings of the Algorithms - ESA 2013, 2013

2012

Smoothed analysis of left-to-right maxima with applications.

Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau

ACM Trans. Algorithms, 2012

StreamKM++: A clustering algorithm for data streams.

Marcel R. Ackermann, Marcus Märtens, Christoph Raupach, Kamil Swierkot, Christiane Lammersen, Christian Sohler

ACM J. Exp. Algorithmics, 2012

Finding Cycles and Trees in Sublinear Time.

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

Electron. Colloquium Comput. Complex., 2012

Almost Optimal Canonical Property Testers for Satisfiability.

Christian Sohler

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness.

Frank Hellweg, Christian Sohler

Proceedings of the Algorithms - ESA 2012, 2012

2011

Subspace embeddings for the L₁-norm with applications.

Christian Sohler, David P. Woodruff

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Tolerant Algorithms.

Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff

Proceedings of the Algorithms - ESA 2011, 2011

2010

Sublinear Clustering.

Artur Czumaj, Christian Sohler

Proceedings of the Encyclopedia of Machine Learning, 2010

Clustering for metric and nonmetric distance measures.

Marcel R. Ackermann, Johannes Blömer, Christian Sohler

ACM Trans. Algorithms, 2010

Small Space Representations for Metric Min-sum <i>k</i>-Clustering and Their Applications.

Artur Czumaj, Christian Sohler

Theory Comput. Syst., 2010

Testing Expansion in Bounded-Degree Graphs.

Artur Czumaj, Christian Sohler

Comb. Probab. Comput., 2010

Coresets and Sketches for High Dimensional Subspace Approximation Problems.

Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Testing Monotone Continuous Distributions on High-dimensional Real Cubes.

Michal Adamaszek, Artur Czumaj, Christian Sohler

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Testing Euclidean Spanners.

Frank Hellweg, Melanie Schmidt, Christian Sohler

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear-time Algorithms.

Artur Czumaj, Christian Sohler

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Monotone Continuous Distributions on High-Dimensional Real Cubes.

Michal Adamaszek, Artur Czumaj, Christian Sohler

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Euclidean Spanners.

Frank Hellweg, Melanie Schmidt, Christian Sohler

Proceedings of the Algorithms, 2010

StreamKM++: A Clustering Algorithms for Data Streams.

Marcel R. Ackermann, Christiane Lammersen, Marcus Märtens, Christoph Raupach, Christian Sohler, Kamil Swierkot

Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, 2010

2009

A sublinear-time approximation scheme for bin packing.

Tugkan Batu, Petra Berenbrink, Christian Sohler

Theor. Comput. Sci., 2009

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.

Artur Czumaj, Asaf Shapira, Christian Sohler

SIAM J. Comput., 2009

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.

Artur Czumaj, Christian Sohler

SIAM J. Comput., 2009

Streaming Embeddings with Slack.

Christiane Lammersen, Anastasios Sidiropoulos, Christian Sohler

Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

<i>d</i>-Dimensional Knapsack in the Streaming Model.

Sumit Ganguly, Christian Sohler

Proceedings of the Algorithms, 2009

2008

Testing Euclidean minimum spanning trees in the plane.

Artur Czumaj, Christian Sohler

ACM Trans. Algorithms, 2008

A Fast k-Means Implementation Using Coresets.

Gereon Frahling, Christian Sohler

Int. J. Comput. Geom. Appl., 2008

Sampling in Dynamic Data Streams and Applications.

Gereon Frahling, Piotr Indyk, Christian Sohler

Int. J. Comput. Geom. Appl., 2008

Clustering for metric and non-metric distance measures.

Marcel R. Ackermann, Johannes Blömer, Christian Sohler

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Facility Location in Dynamic Geometric Data Streams.

Christiane Lammersen, Christian Sohler

Proceedings of the Algorithms, 2008

08341 Executive Summary - Sublinear Algorithms.

Artur Czumaj, S. Muthukrishnan, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

08341 Abstracts Collection - Sublinear Algorithms.

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

2007

Sublinear-time approximation algorithms for clustering via random sampling.

Artur Czumaj, Christian Sohler

Random Struct. Algorithms, 2007

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs.

Artur Czumaj, Asaf Shapira, Christian Sohler

Electron. Colloquium Comput. Complex., 2007

On testable properties in bounded degree graphs.

Artur Czumaj, Christian Sohler

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Estimating Clustering Indexes in Data Streams.

Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Christian Sohler

Proceedings of the Algorithms, 2007

A PTAS for k-means clustering based on weak coresets.

Dan Feldman, Morteza Monemizadeh, Christian Sohler

Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007

Efficient Kinetic Data Structures for MaxCut.

Artur Czumaj, Gereon Frahling, Christian Sohler

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006

A Distributed Algorithm for the Facility Location Problem.

Joachim Gehweiler, Christiane Lammersen, Christian Sohler

Electron. Notes Discret. Math., 2006

Sublinear-Time Algorithms.

Artur Czumaj, Christian Sohler

Bull. EATCS, 2006

A distributed <i>O</i>(1)-approximation algorithm for the uniform facility location problem.

Joachim Gehweiler, Christiane Lammersen, Christian Sohler

Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006

Counting triangles in data streams.

Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, Christian Sohler

Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

2005

Testing hypergraph colorability.

Artur Czumaj, Christian Sohler

Theor. Comput. Sci., 2005

Abstract Combinatorial Programs and Efficient Property Testers.

Artur Czumaj, Christian Sohler

SIAM J. Comput., 2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

SIAM J. Comput., 2005

Fast reconstruction of Delaunay triangulations.

Christian Sohler

Comput. Geom., 2005

Coresets in dynamic geometric data streams.

Gereon Frahling, Christian Sohler

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Facility Location in Sublinear Time.

Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Average case complexity of Voronoi diagrams of n sites from the unit cube.

Marcin Bienkowski, Valentina Damerow, Friedhelm Meyer auf der Heide, Christian Sohler

Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005

05291 Abstracts Collection -- Sublinear Algorithms.

Artur Czumaj, S. Muthu Muthukrishnan, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004

Reducing State Changes with a Pipeline Buffer.

Jens Krokowski, Harald Räcke, Christian Sohler, Matthias Westermann

Proceedings of the 9th International Fall Workshop on Vision, Modeling, and Visualization, 2004

Sublinear-Time Approximation for Clustering Via Random Sampling.

Artur Czumaj, Christian Sohler

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Extreme Points Under Random Noise.

Valentina Damerow, Christian Sohler

Proceedings of the Algorithms, 2004

Labeling Smart Dust.

Vikas Bansal, Friedhelm Meyer auf der Heide, Christian Sohler

Proceedings of the Algorithms, 2004

2003

Property testing and geometry.

Christian Sohler

PhD thesis, 2003

Randomized Pursuit-Evasion In Graphs.

Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking

Comb. Probab. Comput., 2003

Sublinear-time approximation of Euclidean minimum spanning tree.

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Smoothed Motion Complexity.

Valentina Damerow, Friedhelm Meyer auf der Heide, Harald Räcke, Christian Scheideler, Christian Sohler

Proceedings of the Algorithms, 2003

2002

Online Scheduling for Sorting Buffers.

Harald Räcke, Christian Sohler, Matthias Westermann

Proceedings of the Algorithms, 2002

2001

Soft kinetic data structures.

Artur Czumaj, Christian Sohler

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Testing Hypergraph Coloring.

Artur Czumaj, Christian Sohler

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Property Testing with Geometric Queries.

Artur Czumaj, Christian Sohler

Proceedings of the Algorithms, 2001

2000

Property Testing in Computational Geometry.

Artur Czumaj, Christian Sohler, Martin Ziegler

Proceedings of the Algorithms, 2000

Computing Cut Numbers.

Christian Sohler, Martin Ziegler

Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999

Generating random star-shaped polygons.

Christian Sohler

Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1997

Encoding a triangulation as a permutation of its point set.

Markus Denny, Christian Sohler

Proceedings of the 9th Canadian Conference on Computational Geometry, 1997