Efficient Testing of Large Graphs

By Noga Alon, E. Fischer, Michael Krivelevich, Mario Szegedy. 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), 2000

384 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/06650b048396e1a939dec448f584a374ade8966e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing (2007, unknown): “Alon, Fisher, Krivelevich and Szegedy [3]”
Surveys in Combinatorics 2011: Hypergraph Turán problems (2011, background): “Graph limits were first studied by Borgs, Chayes, Lovász, Sós and Vesztergombi (2003 unpublished and [24]) and by Lovász and Szegedy [126].”
Szemerédi’s Lemma for the Analyst (2007, background): “Such a “super-strong” Regularity Lemma was proved by Alon, Fisher, Krivelevich and Szegedy [1, 2].”
Correlation Clustering (2002, background): “This problem is also closely related to work on testing graph properties of [13, 19, 1].”
An Arithmetic Regularity Lemma, An Associated Counting Lemma, and Applications (2010, background): “The reader will easily confirm that in this case we have Ψ([1]) = R(1, 1, 1, 1) ⊕ R(0, 1, 2, 3) and Ψ([2]) = R(1, 1, 1, 1) ⊕ R(0, 1, 2, 3) ⊕ R(0, 0, 1, 3) and Ψ([3]) = R(1, 1, 1, 1) ⊕ R(0, 1, 2, 3) ⊕ R(0, 0, 1, 3) + R(0, 0, 0, 1) = R(4).”
Introduction to Property Testing (2017, background): “56 In contrast, the Ω(k) lower bound established in [114] (following [8]) refers to the natural property of testing whether a k-vertex graph consists of two isomorphic copies of some k/2-vertex graph.”
Regularity Lemmas for Graphs (2010, background): “Here we will not further discuss this line of research and we refer the interested reader to the surveys [15, 23, 31] and the references therein.”
Testing that distributions are close (2000, methodology): “[1] show a canonical form for algorithms for testing graph properties.”
On exchangeable random variables and the statistics of large graphs and hypergraphs (2008, background): “In fact, Elek and Szegedy’s use of ultralimits has a predecessor in Hoover’s approach to the basic representation theorems for exchangeable arrays of random variables, as outlined in [42].”
Many T copies in H-free graphs (2015, unknown): “(ii) For any k ≥ 2, ex(n,K3, C2k+1) ≤ 16(k−1)3 ex(dn/2e, C2k).”