20 citations · 31 across the 15 of their papers we have counts for
12 papers · 1 filter
Optimal non-adaptive algorithm for edge estimation
Arijit Bishnu, Debarshi Chanda, Buddha Dev Das +2
We present a simple nonadaptive randomized algorithm that estimates the number of edges in a simple, unweighted, undirected graph, possibly containing isolated vertices, using only…
On Estimating Degree Distribution in Streaming and Query Models
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
Given a graph with vertices and edges, let denote its complementary cumulative degree histogram (CCDH), and let be the -index…
Arboricity Matters in Triangle Counting with Random Edges
Arijit Bishnu, Debarshi Chanda, Gopinath Mishra
Given a simple, unweighted, undirected graph with and , and parameters , along with Degree, Neighbour, Pair and RandomEdge query acce…
Near Uniform Triangle Sampling Over Adjacency List Graph Streams
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
Triangle counting and sampling are two fundamental problems for streaming algorithms. Arguably, designing sampling algorithms is more challenging than their counting variants. It m…
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…
On the Complexity of Triangle Counting using Emptiness Queries
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra
Beame et al. [ITCS 2018 & TALG 2021] introduced and used the Bipartite Independent Set (BIS) and Independent Set (IS) oracle access to an unknown, simple, unweighted and undirected…
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…
On Triangle Estimation using Tripartite Independent Set Queries
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh +1
Estimating the number of triangles in a graph is one of the most fundamental problems in sublinear algorithms. In this work, we provide an algorithm that approximately counts the n…
Almost optimal query algorithm for hitting set using a subset query
Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay +2
Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity.…