Christian Sohler

According to our database1, Christian Sohler authored at least 119 papers between 1997 and 2018.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Dissection-BKW.
IACR Cryptology ePrint Archive, 2018

Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering.
CoRR, 2018

On Coresets for Logistic Regression.
CoRR, 2018

Estimating Graph Parameters from Random Order Streams.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Approximating the Spectrum of a Graph.
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.
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018

Dissection-BKW.
Proceedings of the Advances in Cryptology - CRYPTO 2018, 2018

2017
Sublinear Clustering.
Proceedings of the Encyclopedia of Machine Learning and Data Mining, 2017

Random projections for Bayesian regression.
Statistics and Computing, 2017

Approximating the Spectrum of a Graph.
CoRR, 2017

Estimating Graph Parameters from Random Order Streams.
CoRR, 2017

Testable Bounded Degree Graph Properties Are Random Order Streamable.
CoRR, 2017

Clustering High Dimensional Dynamic Data Streams.
CoRR, 2017

Testing for Forbidden Order Patterns in an Array.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Clustering High Dimensional Dynamic Data Streams.
Proceedings of the 34th International Conference on Machine Learning, 2017

Testable Bounded Degree Graph Properties Are Random Order Streamable.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Distributed Monitoring of Network Properties: The Power of Hybrid Networks.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Theoretical Analysis of the k-Means Algorithm - A Survey.
Proceedings of the Algorithm Engineering - Selected Results and Surveys, 2016

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

Relating two property testing models for bounded degree directed graphs.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Clustering time series under the Fréchet distance.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Diameter and k-Center in Sliding Windows.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Probabilistic k-Median Clustering in Data Streams.
Theory Comput. Syst., 2015

Random projections for Bayesian regression.
CoRR, 2015

Clustering time series under the Fréchet distance.
CoRR, 2015

Testing Cluster Structure of Graphs.
CoRR, 2015

Testing Cluster Structure of Graphs.
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.
Proceedings of the Approximation, 2015

2014
Finding cycles and trees in sublinear time.
Random Struct. Algorithms, 2014

Asymptotically exact streaming algorithms.
CoRR, 2014

Planar Graphs: Random Walks and Bipartiteness Testing.
CoRR, 2014

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

Analysis of Agglomerative Clustering.
Algorithmica, 2014

What Does the Local Structure of a Planar Graph Tell Us About Its Global Structure?
Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Signal/Background Classification of Time Series for Biological Virus Detection.
Proceedings of the Pattern Recognition - 36th German Conference, 2014

Smallest enclosing ball for probabilistic data.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

2013
Every Property of Hyperfinite Graphs Is Testable.
SIAM J. Comput., 2013

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

Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

(1+ Є)-approximation for facility location in data streams.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

BICO: BIRCH Meets Coresets for k-Means Clustering.
Proceedings of the Algorithms - ESA 2013, 2013

2012
Smoothed analysis of left-to-right maxima with applications.
ACM Trans. Algorithms, 2012

StreamKM++: A clustering algorithm for data streams.
ACM Journal of Experimental Algorithmics, 2012

Finding Cycles and Trees in Sublinear Time.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Probabilistic k-Median Clustering in Data Streams.
Proceedings of the Approximation and Online Algorithms - 10th International Workshop, 2012

Almost Optimal Canonical Property Testers for Satisfiability.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness.
Proceedings of the Algorithms - ESA 2012, 2012

2011
Subspace embeddings for the L1-norm with applications.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Every property of hyperfinite graphs is testable.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Analysis of Agglomerative Clustering.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Planar Graphs: Random Walks and Bipartiteness Testing.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Tolerant Algorithms.
Proceedings of the Algorithms - ESA 2011, 2011

2010
Sublinear Clustering.
Proceedings of the Encyclopedia of Machine Learning, 2010

Clustering for metric and nonmetric distance measures.
ACM Trans. Algorithms, 2010

Small Space Representations for Metric Min-sum k-Clustering and Their Applications.
Theory Comput. Syst., 2010

Testing Expansion in Bounded-Degree Graphs.
Combinatorics, Probability & Computing, 2010

Analysis of Agglomerative Clustering
CoRR, 2010

Finding Cycles and Trees in Sublinear Time
CoRR, 2010

Coresets and Sketches for High Dimensional Subspace Approximation Problems.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Testing Monotone Continuous Distributions on High-dimensional Real Cubes.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

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

Sublinear-time Algorithms.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Monotone Continuous Distributions on High-Dimensional Real Cubes.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Euclidean Spanners.
Proceedings of the Algorithms, 2010

StreamKM++: A Clustering Algorithms for Data Streams.
Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, 2010

2009
A sublinear-time approximation scheme for bin packing.
Theor. Comput. Sci., 2009

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.
SIAM J. Comput., 2009

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.
SIAM J. Comput., 2009

Streaming Embeddings with Slack.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

d-Dimensional Knapsack in the Streaming Model.
Proceedings of the Algorithms, 2009

2008
Testing Euclidean minimum spanning trees in the plane.
ACM Trans. Algorithms, 2008

A Fast k-Means Implementation Using Coresets.
Int. J. Comput. Geometry Appl., 2008

Sampling in Dynamic Data Streams and Applications.
Int. J. Comput. Geometry Appl., 2008

Clustering for metric and non-metric distance measures.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Facility Location in Dynamic Geometric Data Streams.
Proceedings of the Algorithms, 2008

08341 Executive Summary - Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

08341 Abstracts Collection - Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

2007
Sublinear-time approximation algorithms for clustering via random sampling.
Random Struct. Algorithms, 2007

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Small Space Representations for Metric Min-Sum k -Clustering and Their Applications.
Proceedings of the STACS 2007, 2007

On testable properties in bounded degree graphs.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Testing Expansion in Bounded-Degree Graphs.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Estimating Clustering Indexes in Data Streams.
Proceedings of the Algorithms, 2007

A PTAS for k-means clustering based on weak coresets.
Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, 2007

Efficient Kinetic Data Structures for MaxCut.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006
A Distributed Algorithm for the Facility Location Problem.
Electronic Notes in Discrete Mathematics, 2006

Sublinear-Time Algorithms.
Bulletin of the EATCS, 2006

A distributed O(1)-approximation algorithm for the uniform facility location problem.
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.
Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2006

A fast k-means implementation using coresets.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005
Testing hypergraph colorability.
Theor. Comput. Sci., 2005

Abstract Combinatorial Programs and Efficient Property Testers.
SIAM J. Comput., 2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.
SIAM J. Comput., 2005

Fast reconstruction of Delaunay triangulations.
Comput. Geom., 2005

Coresets in dynamic geometric data streams.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Facility Location in Sublinear Time.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Average case complexity of Voronoi diagrams of n sites from the unit cube.
Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005

05291 Abstracts Collection -- Sublinear Algorithms.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

Sampling in dynamic data streams and applications.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005

2004
Reducing State Changes with a Pipeline Buffer.
Proceedings of the Vision, 2004

Estimating the weight of metric minimum spanning trees in sublinear-time.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Sublinear-Time Approximation for Clustering Via Random Sampling.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Extreme Points Under Random Noise.
Proceedings of the Algorithms, 2004

Labeling Smart Dust.
Proceedings of the Algorithms, 2004

2003
Property testing and geometry.
PhD thesis, 2003

Randomized Pursuit-Evasion In Graphs.
Combinatorics, Probability & Computing, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Smoothed Motion Complexity.
Proceedings of the Algorithms, 2003

2002
Randomized Pursuit-Evasion in Graphs.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Abstract Combinatorial Programs and Efficient Property Testers.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Online Scheduling for Sorting Buffers.
Proceedings of the Algorithms, 2002

2001
Soft kinetic data structures.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Testing Hypergraph Coloring.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Property Testing with Geometric Queries.
Proceedings of the Algorithms, 2001

2000
Property Testing in Computational Geometry.
Proceedings of the Algorithms, 2000

Computing Cut Numbers.
Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1999
Generating random star-shaped polygons.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

Fast reconstruction of delaunay triangulations.
Proceedings of the 11th Canadian Conference on Computational Geometry, 1999

1997
Encoding a triangulation as a permutation of its point set.
Proceedings of the 9th Canadian Conference on Computational Geometry, 1997


  Loading...