4 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…
Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression
Debabrota Basu, Sourav Chakraborty, Debarshi Chanda +3
Assessing whether a sample survey credibly represents the population is a critical question for ensuring the validity of downstream research. Generally, this problem reduces to est…
Testing Credibility of Public and Private Surveys through the Lens of Regression
Debabrota Basu, Sourav Chakraborty, Debarshi Chanda +3
Testing whether a sample survey is a credible representation of the population is an important question to ensure the validity of any downstream research. While this problem, in ge…