159 citations · 313 across the 22 of their papers we have counts for
26 papers
Property Testing of Computational Networks
Artur Czumaj, Christian Sohler
In this paper we initiate the study of \emph{property testing of weighted computational networks viewed as computational devices}. Our goal is to design property testing algorithms…
Testing Depth First Search Numbering
Artur Czumaj, Christian Sohler, Stefan Walzer
Property Testing is a formal framework to study the computational power and complexity of sampling from combinatorial objects. A central goal in standard graph property testing is…
Constant Approximation for Normalized Modularity and Associations Clustering
Jakub Łącki, Vahab Mirrokni, Christian Sohler
We study the problem of graph clustering under a broad class of objectives in which the quality of a cluster is defined based on the ratio between the number of edges in the cluste…
Spectral Clustering Oracles in Sublinear Time
Grzegorz Gluch, Michael Kapralov, Silvio Lattanzi +2
Given a graph that can be partitioned into disjoint expanders with outer conductance upper bounded by , can we efficiently construct a small space data structure th…
Fast and Accurate -means++ via Rejection Sampling
Vincent Cohen-Addad, Silvio Lattanzi, Ashkan Norouzi-Fard +2
-means++ \cite{arthur2007k} is a widely used clustering algorithm that is easy to implement, has nice theoretical guarantees and strong empirical performance. Despite its wide a…
A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)
Artur Czumaj, Christian Sohler
The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area…