Fetching the paper…
Reading the bibliography…
We study the task of estimating the number of edges in a graph with access to only an independent set oracle.
The detection of defective members of large populations
R. Dorfman · 1943
Earlier work this paper cites.
The complexity of approximate counting (preliminary version)
L. Stockmeyer · 1983
Earlier work this paper cites.
On approximation algorithms for #P
L. Stockmeyer · 1985
Earlier work this paper cites.
Group testing for estimating infection rates and probabilities of disease transmission
W. H. Swallow · 1985
Earlier work this paper cites.
Using group testing to estimate a proportion, and to test the b inomial model
C. L. Chen and W. H. Swallow · 1990
Earlier work this paper cites.
Disk graphs: A short survey
A. V Fishkin · 2003
Earlier work this paper cites.
Complement factor H polymorphism in age-related macular degeneration
R. J. Klein, C. Zeiss, E. Chew, J.-Y. Tsai, R.S. Sackler, C. Haynes, A.K. Henning, J.P. SanGiovanni, S.M. Mane, S.T. Mayne, R.B. Bracken, F.L. Ferris, J. Ott, C. Barnstable, and J. Noh · 2005
Earlier work this paper cites.
Concentration inequalities and martingale inequalities: A survey
F. Chung and L. Lu · 2006
Earlier work this paper cites.
On sums of independent random variables with unbounded variance and estimating the average degree in a graph
U. Feige · 2006
Earlier work this paper cites.
On Approximating the Depth and Related Problems
B. Aronov and S. Har-Peled · 2008
Earlier work this paper cites.
Approximating average parameters of graphs
O. Goldreich and D. Ron · 2008
Cited alongside, same era.
Concentration of Measure for the Analysis of Randomized Algorithms
D. P. Dubhashi and A. Panconesi · 2009
Cited alongside, same era.
Counting stars and other small subgraphs in sublinear-time
M. Gonen, D. Ron, and Y. Shavitt · 2011
Cited alongside, same era.
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
K. Onak, D. Ron, M. Rosen, and R. Rubinfeld · 2012
Cited alongside, same era.
Comparing the strength of query types in property testing: The case of k k -colorability
I. Ben-Eliezer, T. Kaufman, M. Krivelevich, and D. Ron · 2013
Cited alongside, same era.
Identifying the most connected vertices in hidden bipartite graphs using group testing
J. Wang, E. Lo, and M. L. Yiu · 2013
Approximately counting triangles in sublinear time
T. Eden, A. Levi, D. Ron, and C. Seshadhri · 2017
Closest in time.
On Approximating the Number of k k -cliques in Sublinear Time
T. Eden, D. Ron, and C. Seshadhri · 2017
Closest in time.
Sublinear-time algorithms for counting star subgraphs via edge sampling
Maryam Aliakbarpour, Amartya Shankha Biswas, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee · 2018
Closest in time.
Edge estimation with independent set oracles
P. Beame, S. Har-Peled , S. Natarajan Ramamoorthy, C. Rashtchian, and M. Sinha · 2018
Closest in time.
Fine-grained reductions from approximate counting to decision
Holger Dell and John Lapinskas · 2018
Closest in time.
On sampling edges almost uniformly
T. Eden and W. Rosenbaum · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Shortest paths in intersection graphs of unit disks
S. Cabello and M. Jejčič · 2015
Cited alongside, same era.
A simpler sublinear algorithm for approximating the triangle count
C. Seshadhri · 2015
Cited alongside, same era.
Estimating the number of defectives with group testing
M. Falahatgar, A. Jafarpour, A. Orlitsky, V. Pichapati, and A. T. Suresh · 2016
Cited alongside, same era.
The power of an example: Hidden set size approximation using group queries and conditional sampling
D. Ron and G. Tsur · 2016
Cited alongside, same era.
Closest in time.
Hyperedge estimation using polylogarithmic subset queries
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra · 2019
Closest in time.
Triangle estimation using tripartite independent set queries
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, and Gopinath Mishra · 2019
Closest in time.
Nearly optimal edge estimation with independent set queries
Xi Chen, Amit Levi, and Erik Waingarten · 2020
Closest in time.
Approximately counting and sampling small witnesses using a colourful decision oracle
Holger Dell, John Lapinskas, and Kitty Meeks · 2020
Closest in time.