3 papers
cs.DS2026
Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
Vihan Shah
We study the problem of estimating the size of the maximum matching in the sublinear-time setting. This problem has been extensively studied, with several known upper and lower bou…
cs.DS2026
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…
cs.DS2024
Learning-augmented Maximum Independent Set
Vladimir Braverman, Prathamesh Dharangutte, Vihan Shah +1
We study the Maximum Independent Set (MIS) problem on general graphs within the framework of learning-augmented algorithms. The MIS problem is known to be NP-hard and is also NP-ha…