11 citations · 21 across the 13 of their papers we have counts for
13 papers · 1 filter
Private Graph Property Testing
Hendrik Fichtenberger, Abigail Gentle, Tamalika Mukherjee +1
Graph property testing asks whether a massive graph satisfies a given property, or is far from doing so, using only a sublinear number of queries to the graph. Since property teste…
A Differentially Private Clustering Algorithm for Well-Clustered Graphs
Weiqiang He, Hendrik Fichtenberger, Pan Peng
We study differentially private (DP) algorithms for recovering clusters in well-clustered graphs, which are graphs whose vertex set can be partitioned into a small number of sets,…
Optimal Fully Dynamic -Center Clustering for Adaptive and Oblivious Adversaries
MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger +4
In fully dynamic clustering problems, a clustering of a given data set in a metric space must be maintained while it is modified through insertions and deletions of individual poin…
Approximately Counting Subgraphs in Data Streams
Hendrik Fichtenberger, Pan Peng
Estimating the number of subgraphs in data streams is a fundamental problem that has received great attention in the past decade. In this paper, we give improved streaming algorith…
Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
Hendrik Fichtenberger, Monika Henzinger, Jalaj Upadhyay
We study fine-grained error bounds for differentially private algorithms for counting under continual observation. Our main insight is that the matrix mechanism when using lower-tr…
On fully dynamic constant-factor approximation algorithms for clustering problems
Hendrik Fichtenberger, Monika Henzinger, Andreas Wiese
Clustering is an important task with applications in many fields of computer science. We study the fully dynamic setting in which we want to maintain good clusters efficiently when…
Differentially Private Algorithms for Graphs Under Continual Observation
Hendrik Fichtenberger, Monika Henzinger, Lara Ost
Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and…
Consistent k-Clustering for General Metrics
Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard +1
Given a stream of points in a metric space, is it possible to maintain a constant approximate clustering by changing the cluster centers only a small number of times during the ent…
Sampling Arbitrary Subgraphs Exactly Uniformly in Sublinear Time
Hendrik Fichtenberger, Mingze Gao, Pan Peng
We present a simple sublinear-time algorithm for sampling an arbitrary subgraph \emph{exactly uniformly} from a graph with edges, to which the algorithm has access by p…
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…
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…
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
Hendrik Fichtenberger, Reut Levi, Yadu Vasudev +1
We consider one-sided error property testing of -minor freeness in bounded-degree graphs for any finite family of graphs that contains a minor of $K_{2,k…
PROBI: A Heuristic for the probabilistic k-median problem
Hendrik Fichtenberger, Melanie Schmidt
We develop the heuristic PROBI for the probabilistic Euclidean k-median problem based on a coreset construction by Lammersen et al. Our algorithm computes a summary of the data and…