Property Testing in Bounded Degree Graphs

By Oded Goldreich, Dana Ron. Symposium on the Theory of Computing, 2002

390 citations recorded by the source corpus.

How researchers see this paper

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

Introduction to Property Testing (2017, methodology): “Gaps exist also in models of testing graphs properties (see the results regarding ρ-Clique in [140] and the results regarding cycle-freeness in [147, 81]).”
Distributed Uniformity Testing (2018, background): “It was first considered implicitly in [13, 17], as part of a tester that estimated the expansion of a graph by testing whether the distribution of a short random walk in the graph is uniform, or far from uniform.”
On Multiple Input Problems in Property Testing (2013, methodology): “Other examples include ρ-clique in the dense graphs model [5], and cycle-freeness in the bounded-degree graph model [8].”
Testing that distributions are close (2000, background): “Our results fall within the various frameworks of property testing [22, 13, 14, 7, 21].”
On Testing Expansion in Bounded-Degree Graphs (2000, methodology): “We mention that the Ω ( √ N ) lower bound on “testing expansion” (presented in [5]) continues to hold for the relaxed formulation, provided that λ ′ 1.”
FAST-PPR: scaling personalized pagerank estimation for large graphs (2014, methodology): “Theorem 7.5 of Goldreich and Ron [24] asserts the following: Theorem 5 (Theorem 7.5 of [24]).”