1 citations · 1 across the 1 of their papers we have counts for
8 papers
Faster Counting and Sampling Algorithms using Colorful Decision Oracle
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh +1
In this work, we consider -{\sc Hyperedge Estimation} and -{\sc Hyperedge Sample} problem in a hypergraph in the query…
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming Cube
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
Using geometric techniques like projection and dimensionality reduction, we show that there exists a randomized sub-linear time algorithm that can estimate the Hamming distance bet…
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…
Hyperedge Estimation using Polylogarithmic Subset Queries
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh +1
In this work, we estimate the number of hyperedges in a hypergraph , where denotes the set of vertices and ${\cal F}({\cal…
Structural Parameterization for Graph Deletion Problems over Data Streams
Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay +2
The study of parameterized streaming complexity on graph problems was initiated by Fafianie et al. (MFCS'14) and Chitnis et al. (SODA'15 and SODA'16). Simply put, the main goal is…