Fetching the paper…
Reading the bibliography…
In the subgraph counting problem, we are given a input graph $G(V, E)$ and a target graph $H$; the goal is to estimate the number of occurrences of $H$ in $G$.
Some complexity questions related to distributive computing (preliminary report)
A. C. Yao · 1979
Earlier work this paper cites.
On the number of subgraphs of prescribed type of graphs with a given number of edges
N. Alon · 1981
Earlier work this paper cites.
Lower bounds by probabilistic arguments (extended abstract)
A. C. Yao · 1983
Earlier work this paper cites.
Arboricity and subgraph listing algorithms
N. Chiba and T. Nishizeki · 1985
Earlier work this paper cites.
The probabilistic communication complexity of set intersection
B. Kalyanasundaram and G. Schnitger · 1992
Earlier work this paper cites.
On the distributional complexity of disjointness
A. A. Razborov · 1992
Earlier work this paper cites.
On the number of copies of one hypergraph in another
E. Friedgut and J. Kahn · 1998
Earlier work this paper cites.
Information theory methods in communication complexity
Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Reductions in streaming algorithms, with an application to counting triangles in graphs
Z. Bar-Yossef, R. Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Network motifs: simple building blocks of complex networks
R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon · 2002
Earlier work this paper cites.
Structural Holes and Good Ideas
S. Burt · 2004
Earlier work this paper cites.
Estimating the weight of metric minimum spanning trees in sublinear-time
A. Czumaj and C. Sohler · 2004
Earlier work this paper cites.
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
U. Feige · 2004
Earlier work this paper cites.
Tight bounds for testing bipartiteness in general graphs
T. Kaufman, M. Krivelevich, and D. Ron · 2004
Earlier work this paper cites.
Relational Graph Analysis with Real-World Constraints: An Application in IRS Tax Fraud Detection
E. Bloedorn, N. Rothleder, D. DeBarr, and L. Rosen · 2005
Earlier work this paper cites.
Approximating the minimum spanning tree weight in sublinear time
B. Chazelle, R. Rubinfeld, and L. Trevisan · 2005
Earlier work this paper cites.
Approximating the weight of the euclidean minimum spanning tree in sublinear time
A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, and C. Sohler · 2005
Earlier work this paper cites.
New streaming algorithms for counting triangles in graphs
H. Jowhari and M. Ghodsi · 2005
Cited alongside, same era.
Counting triangles in data streams
L. S. Buriol, G. Frahling, S. Leonardi, A. Marchetti-Spaccamela, and C. Sohler · 2006
Cited alongside, same era.
Sampling from large graphs
J. Leskovec and C. Faloutsos · 2006
Cited alongside, same era.
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
M. Parnas and D. Ron · 2007
Cited alongside, same era.
Size bounds and query plans for relational joins
A. Atserias, M. Grohe, and D. Marx · 2008
Cited alongside, same era.
Approximating average parameters of graphs
O. Goldreich and D. Ron · 2008
Cited alongside, same era.
Approximately counting triangles in sublinear time
T. Eden, A. Levi, D. Ron, and C. Seshadhri · 2015
Later among the works it cites.
Estimating centrality statistics for complete and sampled networks: Some approaches and complications
J. Lee and J. Pfeffer · 2015
Later among the works it cites.
Catching the head, tail, and everything in between: A streaming algorithm for the degree distribution
O. Simpson, C. Seshadhri, and A. McGregor · 2015
Later among the works it cites.
Better algorithms for counting triangles in data streams
A. McGregor, S. Vorotnikova, and H. T. Vu · 2016
Later among the works it cites.
Towards tighter space bounds for counting triangles and other substructures in graph streams
S. K. Bera and A. Chakrabarti · 2017
Later among the works it cites.
Distribution testing lower bounds via reductions from communication complexity
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Constant-time approximation algorithms via local improvements
H. N. Nguyen and K. Onak · 2008
Cited alongside, same era.
Local graph partitions for approximation and testing
A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak · 2009
Cited alongside, same era.
An improved constant-time approximation algorithm for maximum matchings
Y. Yoshida, M. Yamamoto, and H. Ito · 2009
Cited alongside, same era.
Counting stars and other small subgraphs in sublinear time
M. Gonen, D. Ron, and Y. Shavitt · 2010
Cited alongside, same era.
Property testing lower bounds via communication complexity
E. Blais, J. Brody, and K. Matulef · 2011
Cited alongside, same era.
Counting arbitrary subgraphs in data streams
D. M. Kane, K. Mehlhorn, T. Sauerwald, and H. Sun · 2012
Cited alongside, same era.
E. Blais, C. L. Canonne, and T. Gur · 2017
Later among the works it cites.
A second look at counting triangles in graph streams (corrected)
G. Cormode and H. Jowhari · 2017
Later among the works it cites.
Sublinear time estimation of degree distribution moments: The degeneracy connection
T. Eden, D. Ron, and C. Seshadhri · 2017
Later among the works it cites.
Introduction to Property Testing
O. Goldreich · 2017
Later among the works it cites.
A hybrid sampling scheme for triangle counting
J. Kallaugher and E. Price · 2017
Later among the works it cites.
Sublinear-time algorithms for counting star subgraphs via edge sampling
M. Aliakbarpour, A. S. Biswas, T. Gouleakis, J. Peebles, R. Rubinfeld, and A. Yodpinyanee · 2018
Closest in time.
On approximating the number of k-cliques in sublinear time
T. Eden, D. Ron, and C. Seshadhri · 2018
Closest in time.
Lower bounds for approximating graph parameters via communication complexity
T. Eden and W. Rosenbaum · 2018
Closest in time.
On sampling edges almost uniformly
T. Eden and W. Rosenbaum · 2018
Closest in time.
The sketching complexity of graph and hypergraph counting
J. Kallaugher, M. Kapralov, and E. Price · 2018
Closest in time.
Worst-case optimal join algorithms
H. Q. Ngo, E. Porat, C. Ré, and A. Rudra · 2018
Closest in time.