Debarshi Chanda

most citedArboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries

1 citations · 1 across the 3 of their papers we have counts for

collaborators

4 papers

cs.DS2025

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…

cs.DS2025

Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size

Debarshi Chanda

We propose a randomized algorithm with query access that given a graph $G$ with arboricity $α$ , and average degree $d$ , makes $O (\frac{α}{ε ^{2} d})$ \te…

cs.DS2025

Towards Tight Bounds for Estimating Degree Distribution in Streaming and Query Models

Arijit Bishnu, Debarshi Chanda, Gopinath Mishra

The degree distribution of a graph $G = (V, E)$ , $∣ V ∣ = n$ , $∣ E ∣ = m$ is one of the most fundamental objects of study in the analysis of graphs as it embodies relationship among entities.…

cs.DS2025★ 1 cited

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries

Arijit Bishnu, Debarshi Chanda, Gopinath Mishra

Given a simple, unweighted, undirected graph $G = (V, E)$ with $∣ V ∣ = n$ and $∣ E ∣ = m$ , and parameters $0 < ε, δ < 1$ , along with \texttt{Degree}, \texttt{Neighbour}, \texttt{Edge…