Introduction to Property Testing

By Oded Goldreich. 2017

397 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, methodology): “We point out that the above formulation encompasses both density and parameter estimation, as well as distribution testing (see e.g. [Rub12, Can15] and [Gol17] for a survey of property and distribution testing).”
Hypothesis Testing for High-Dimensional Multinomials: A Selective Review (2017, background): “…theory and theoretical computer science and we provide an overview of some important results from these different communities in this paper.2 2Theoretical computer science centric surveys of a subset of these results include the papers Rubinfeld (2012), Goldreich (2017) and Canonne (2018).”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “In this section, we only focus on closely related papers and we refer an interested reader to surveys and books [13], [21], [34], [43] for a comprehensive treatment.”
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit (2019, methodology): “…work culminated in efﬁcient and sample-optimal testing algorithms [Pan08, VV17, ADK15, Gol16, DGPP18]; we refer the reader to the surveys [Rub12, Can15, BW18], as well as the recent book [Gol17] (Chapter 11) for further details on identity testing, and the more general ﬁeld of distribution testing.”
Distributed Uniformity Testing (2018, background): “At the heart of collisionbased uniformity testers is the following well-known property (see the textbook [16]):”
Test without Trust: Optimal Locally Private Distribution Testing (2018, background): “This literature itself spans the last two decades; we refer an interested reader to surveys and books [30, 11, 24, 8] for a comprehensive review.”