4 papers
Bipartite Matching with Few Rounds of Demand Queries
Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah
We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisa…
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…
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…
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…