3 citations · 8 across the 15 of their papers we have counts for
3 papers · 1 filter
Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!
Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra +1
We study a graph coloring problem that is otherwise easy but becomes quite non-trivial in the one-pass streaming model. In contrast to previous graph coloring problems in streaming…
Query Complexity of Global Minimum Cut
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, wh…
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh +2
The disjointness problem - where Alice and Bob are given two subsets of and they have to check if their sets intersect - is a central problem in the world of comm…