7 citations · 21 across the 12 of their papers we have counts for
15 papers
The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation
Chenglin Fan, Wonseok Shin
Consider an unknown graph with vertex degrees , accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query co…
A -Approximation for Weighted Ultrametric Embedding with Outliers
Chenglin Fan
Weighted ultrametric embedding with outliers asks for a minimum weight set of points whose deletion makes the remaining metric an ultrametric, equivalently, leaves no triple with a…
Fitting Metrics and Ultrametrics with Minimum Disagreements
Vincent Cohen-Addad, Chenglin Fan, Euiwoong Lee +1
Given recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the distance between and…
-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy
Chenglin Fan, Ping Li, Xiaoyun Li
When designing clustering algorithms, the choice of initial centers is crucial for the quality of the learned clusters. In this paper, we develop a new initialization scheme, calle…
Breaking the Linear Error Barrier in Differentially Private Graph Distance Release
Chenglin Fan, Ping Li, Xiaoyun Li
Releasing all pairwise shortest path (APSP) distances between vertices on general graphs under weight Differential Privacy (DP) is known as a challenging task. In the previous atte…
Distances Release with Differential Privacy in Tree and Grid Graph
Chenglin Fan, Ping Li
Data about individuals may contain private and sensitive information. The differential privacy (DP) was proposed to address the problem of protecting the privacy of each individual…
Near-Optimal Correlation Clustering with Privacy
Vincent Cohen-Addad, Chenglin Fan, Silvio Lattanzi +4
Correlation clustering is a central problem in unsupervised learning, with applications spanning community detection, duplicate detection, automated labelling and many more. In the…
Fréchet Distance for Uncertain Curves
Kevin Buchin, Chenglin Fan, Maarten Löffler +3
In this paper we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. We define an uncertain curve as a sequence of…
Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams
Chenglin Fan, Benjamin Raichel
While the standard unweighted Voronoi diagram in the plane has linear worst-case complexity, many of its natural generalizations do not. This paper considers two such previously st…
Generalized Metric Repair on Graphs
Chenglin Fan, Anna C. Gilbert, Benjamin Raichel +2
Many modern data analysis algorithms either assume or are considerably more efficient if the distances between the data points satisfy a metric. These algorithms include metric lea…
Skyline Diagram: Efficient Space Partitioning for Skyline Queries
Jinfei Liu, Juncheng Yang, Li Xiong +5
Skyline queries are important in many application domains. In this paper, we propose a novel structure Skyline Diagram, which given a set of points, partitions the plane into a set…
Metric Violation Distance: Revisited and Extended
Chenglin Fan, Benjamin Raichel, Gregory Van Buskirk
Metric data plays an important role in various settings such as metric-based indexing, clustering, classification, and approximation algorithms in general. Due to measurement error…
Generalized Metric Repair on Graphs
Anna C. Gilbert, Rishi Sonthalia
Many modern data analysis algorithms either assume that or are considerably more efficient if the distances between the data points satisfy a metric. These algorithms include metri…
Complexity and Algorithms for the Discrete Fréchet Distance Upper Bound with Imprecise Input
Chenglin Fan, Binhai Zhu
We study the problem of computing the upper bound of the discrete Fréchet distance for imprecise input, and prove that the problem is NP-hard. This solves an open problem posed in…
On the Chain Pair Simplification Problem
Chenglin Fan, Omrit Filtser, Matthew J. Katz +2
The problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones in 3D has led Bereg et al. to pose the Chain Pair Simplification…