Debarshi Chanda

collaborators

5 papers

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 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 $I^\pm$ , and average degree $d$ , makes $O (\frac{I ^}{\pm} ε^{2} d)$ \…

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

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 < ε, I^´ < 1$ , along with \texttt{Degree}, \texttt{Neighbour}, \texttt{Edg…