Debarshi Chanda

most citedArboricity Matters in Triangle Counting with Random Edges

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

collaborators

Showing cs.DSShow all

5 papers · 1 filter

cs.DS2026

From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries

Debarshi Chanda, Buddha Dev Das, Arijit Ghosh +1

We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of In…

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 for Estimating Average Degree of Graphs

Debarshi Chanda

We propose a randomized parameter-oblivious algorithm that, given query access to a graph $G$ with arboricity $α$ , and average degree $d$ , makes $\widetilde{O}\left(\fracα{\varepsi…

cs.DS2025

On Estimating Degree Distribution in Streaming and Query Models

Arijit Bishnu, Debarshi Chanda, Gopinath Mishra

Given a graph $G = (V, E)$ with $n$ vertices and $m$ edges, let $C (d) = ∣ {v \in V : ° (v) \geq d} ∣$ denote its complementary cumulative degree histogram (CCDH), and let $h$ be the $h$ -index…

cs.DS2025★ 1 cited

Arboricity Matters in Triangle Counting with Random Edges

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 Degree, Neighbour, Pair and RandomEdge query acce…