Publications (29)
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 o…
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…
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…
Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
Chenglin Fan, Dahoon Lee, Euiwoong Lee
Correlation Clustering (CC) is a foundational problem in unsupervised learning that models binary similarity relations using labeled graphs. While classical CC has been widely stud…
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…
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…
1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
Dahoon Lee, Chenglin Fan, Euiwoong Lee
Chromatic Correlation Clustering (CCC) generalizes Correlation Clustering by assigning multiple categorical relationships (colors) to edges and imposing chromatic constraints on th…
Verifiable Exponential Mechanism for Median Estimation
Hyukjun Kwon, Chenglin Fan
Differential Privacy (DP) is a rigorous privacy standard widely adopted in data analysis and machine learning. However, its guarantees rely on correctly introducing randomized nois…
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…
A PTAS for -Low Rank Approximation: Solving Dense CSPs over Reals
Vincent Cohen-Addad, Chenglin Fan, Suprovat Ghoshal +4
We consider the Low Rank Approximation problem, where the input consists of a matrix and an integer , and the goal is to find a matrix of…
DP-Muon: Differentially Private Optimization via Matrix-Orthogonalized Momentum
Jihwan Kim, Chenglin Fan
We study differentially private (DP) training with Muon, a matrix-valued optimizer that updates hidden-layer weights using momentum followed by Newton--Schulz orthogonalization. Wh…
Private Approximation of Graph Spectra and Cuts via Spectral Amplifiers
Chenglin Fan, Jingcheng Liu, Pan Peng +2
We study the problem of releasing a synthetic graph that approximates the sizes of all cuts of an input graph under edge-level differential privacy. If one insists on purely additi…
Noise is All You Need: Private Second-Order Convergence of Noisy SGD
Dmitrii Avdiukhin, Michael Dinitz, Chenglin Fan +1
Private optimization is a topic of major interest in machine learning, with differentially private stochastic gradient descent (DP-SGD) playing a key role in both theory and practi…
Learning-Augmented Ski Rental with Discrete Distributions: A Bayesian Approach
Bosun Kang, Hyejun Park, Chenglin Fan
We revisit the classic ski rental problem through the lens of Bayesian decision-making and machine-learned predictions. While traditional algorithms minimize worst-case cost withou…
Robust and Consistent Ski Rental with Distributional Advice
Jihwan Kim, Chenglin Fan
The ski rental problem is a canonical model for online decision-making under uncertainty, capturing the fundamental trade-off between repeated rental costs and a one-time purchase.…
Finding Differentially Private Second Order Stationary Points in Stochastic Minimax Optimization
Difei Xu, Youming Tao, Meng Ding +2
We provide the first study of the problem of finding differentially private (DP) second-order stationary points (SOSP) in stochastic (non-convex) minimax optimization. Existing lit…
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…
Faster Algorithms for Generalized Mean Densest Subgraph Problem
Chenglin Fan, Ping Li, Hanyu Peng
The densest subgraph of a large graph usually refers to some subgraph with the highest average degree, which has been extended to the family of -means dense subgraph objectives…
EALG: Evolutionary Adversarial Generation of Language Model-Guided Generators for Combinatorial Optimization
Ruibo Duan, Yuxin Liu, Xinyao Dong +1
Generating challenging instances is crucial for the evaluation and advancement of combinatorial optimization solvers. In this work, we introduce EALG (Evolutionary Adversarial Gene…
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…
Self-Critique-Guided Curiosity Refinement: Enhancing Honesty and Helpfulness in Large Language Models via In-Context Learning
Duc Hieu Ho, Chenglin Fan
Large language models (LLMs) have demonstrated robust capabilities across various natural language tasks. However, producing outputs that are consistently honest and helpful remain…
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…
Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
Rishi Chandra, Michael Dinitz, Chenglin Fan +1
In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum -cut. We introduce edge-d…
Diffusion Models under Alternative Noise: Simplified Analysis and Sensitivity
Juhyeok Choi, Chenglin Fan
Diffusion models, typically formulated as discretizations of stochastic differential equations (SDEs), have achieved state-of-the-art performance in generative tasks. However, thei…
-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…
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…
Learning Augmented Graph -Clustering
Chenglin Fan, Kijun Shin
Clustering is a fundamental task in unsupervised learning. Previous research has focused on learning-augmented -means in Euclidean metrics, limiting its applicability to complex…
A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
Michael Dinitz, Chenglin Fan, Jingcheng Liu +2
We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected…
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…