6 papers
Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
Vladimir Braverman, Prathamesh Dharangutte, Shreyas Pai +2
We study the dynamic correlation clustering problem with edge label flips. In correlation clustering, we are given a -vertex complete graph whose edges are l…
PWAVEP: Purifying Imperceptible Adversarial Perturbations in 3D Point Clouds via Spectral Graph Wavelets
Haoran Li, Renyang Liu, Hongjia Liu +3
Recent progress in adversarial attacks on 3D point clouds, particularly in achieving spatial imperceptibility and high attack performance, presents significant challenges for defen…
Online Learning with Limited Information in the Sliding Window Model
Vladimir Braverman, Sumegha Garg, Chen Wang +2
Motivated by recent work on the experts problem in the streaming model, we consider the experts problem in the sliding window model. The sliding window model is a well-studied mode…
Relative Error Fair Clustering in the Weak-Strong Oracle Model
Vladimir Braverman, Prathamesh Dharangutte, Shaofeng H. -C. Jiang +4
We study fair clustering problems in a setting where distance information is obtained from two sources: a strong oracle providing exact distances, but at a high cost, and a weak or…
Learning-Augmented Hierarchical Clustering
Vladimir Braverman, Jon C. Ergun, Chen Wang +1
Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together simi…
Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
Nikolai Karpov, Chen Wang
We investigate the sample-memory-pass trade-offs for pure exploration in multi-pass streaming multi-armed bandits (MABs) with the *a priori* knowledge of the optimality gap $Î_{[2…