1 citations · 1 across the 5 of their papers we have counts for
5 papers
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…
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…
Improved Bounds for Estimating Average Degree of Graphs
Debarshi Chanda
We propose a randomized parameter-oblivious algorithm that, given query access to a graph with arboricity , and average degree , makes $\widetilde{O}\left(\fracα{\varepsi…
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…