17 citations · 30 across the 4 of their papers we have counts for
14 papers · 1 filter
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…
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…
Fully dynamic hierarchical diameter k-clustering and k-center
Melanie Schmidt, Christian Sohler
We develop dynamic data structures for maintaining a hierarchical k-center clustering when the points come from a discrete space . Our first data structure is for…
Testable Properties in General Graphs and Random Order Streaming
Artur Czumaj, Hendrik Fichtenberger, Pan Peng +1
We present a novel framework closely linking the areas of property testing and data streaming algorithms in the setting of general graphs. It has been recently shown (Monemizadeh e…
Fair Coresets and Streaming Algorithms for Fair k-Means Clustering
Melanie Schmidt, Chris Schwiegelshohn, Christian Sohler
We study fair clustering problems as proposed by Chierichetti et al. (NIPS 2017). Here, points have a sensitive attribute and all clusters in the solution are required to be balanc…
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
Hendrik Fichtenberger, Pan Peng, Christian Sohler
One of the most fundamental questions in graph property testing is to characterize the combinatorial structure of properties that are testable with a constant number of queries. We…