Showing cs.DSShow all
2 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.DS2024
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Sourav Chakraborty, Eldar Fischer, Arijit Ghosh +3
The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on , where is so large that even reading…