8 papers
Zero Knowledge for Free up to Linear Query Bounds: Quasilinear-Size Constant-Query Zero-Knowledge PCPs
Inhyuk Park, Chenglin Fan
We show that for all polynomials and , every relation in NTIME() has a binary PCP with non-adaptive queries, perfect completeness, soundness error 1/2 and length $…
Optimal High Probability Bounds for Random Order Online Sorting
Chenglin Fan, Mingyu Kang
In random order online sorting, a fixed multiset of real numbers arrives in a uniformly random order. Each value must be placed immediately and irrevocably into an empty positi…
Pseudometric-Weighted Correlation Clustering via Spectral Preclustering
Chenglin Fan, Dahoon Lee, Euiwoong Lee
We study pseudometric-weighted correlation clustering, where every pair of vertices carries a nonnegative disagreement weight and the weights satisfy the triangle inequality. For e…
DP-Muon: Differentially Private Optimization via Matrix-Orthogonalized Momentum
Jihwan Kim, Chenglin Fan
We study differentially private optimization with matrix-orthogonalized momentum. DP-Muon uses conventional global per-example clipping and one Gaussian gradient release per step;…
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.…
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…
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…
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…