5 papers · 1 filter
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.…