Property testing and its connection to learning and approximation

By Oded Goldreich, Shafi Goldwasser, Dana Ron. 1996

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

Distributed Simulation and Distributed Inference (2018, background): “First introduced by Batu et al. [BFR + 00] and Goldreich, Goldwasser, and Ron [GGR98], distribution testing is a branch of property testing [RS96, GGR98], a ﬁeld of theoretical computer science focusing on “ultra-fast” (sublinear-time) algorithms for decision problems.”
The Power of Linear Estimators (2011, background): “This tight bound of Θ(m/ logm) on the number of samples required to yield constant error contrasts with the tight bound of Θ(m) shown in [7], [15] for the related problem of distinguishing a uniform distribution on m samples from one that has constant distance from such a distribution.”
Clustering Large Graphs via the Singular Value Decomposition (2004, background): “¶Supported in part by NSF Grant CCR-6895000 and a Sloan Foundation Fellowship.”
Test without Trust: Optimal Locally Private Distribution Testing (2018, methodology): “wo problems are instances of distribution testing, a sub-area of statistical hypothesis testing focusing on small-sample analysis introduced by Batu et al. [BFR+00] and Goldreich, Goldwasser, and Ron [GGR98]. Our results are comprehensive, and organized along two axes: First, we consider tests that ”
Poisson convergence in the restricted k-partitioning problem (2007, methodology): “It was formalized by Goldreich, Goldwasser, and Ron in [18].”
A quantitative Arrow theorem (2009, background): “As noted in [10], there is an interesting connection between quantitative Arrow statements and the concept of testing introduced in [18, 9] which was studied and used extensively since.”
Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing (2007, background): “, is it 3-colorable? In particular, which parameters can be accurately estimated and which properties can be tested with high probability by looking only at subgraphs on small randomly chosen subsets of the nodes? A precise definition of property testing was given by Goldreich, Goldwasser and Ron [2”
Counting Graph Homomorphisms (2006, background): “This parameter is testable: this fact is nontrivial, and its first proof by Goldreich, Goldwasser and Ron [31] was one of the first important results in Property Testing.”
Introduction to Property Testing (2017, methodology): “The work of Goldreich, Goldwasser, and Ron [140] advocated viewing property testing as a new type of computational problems, rather than as a tool towards program checking [58] (as viewed in [59]) or towards the construction of PCP systems (see below).”