Concepedia

Hierarchy Theorems for Property Testing

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Computational Complexity · 2011 · 21 citations · 23 references

DOI

Concepts

References

23

Property testing and its connection to learning and approximation

Oded Goldreich, Shari Goldwasser, Dana Ron · Journal of the ACM · 1998 · 1.1K citations · Full text

, , +14

A fast and simple randomized parallel algorithm for the maximal independent set problem

Noga Alon, László Babai, Alon Itai · Journal of Algorithms · 1986 · 842 citations

, , +13

Robust Characterizations of Polynomials with Applications to Program Testing

Ronitt Rubinfeld, Madhu Sudan · SIAM Journal on Computing · 1996 · 816 citations

, , +11

Self-testing/correcting with applications to numerical problems

Manuel Blum, Michael Luby, Ronitt Rubinfeld · Journal of Computer and System Sciences · 1993 · 722 citations

, , +12

Simple Constructions of Almost k‐wise Independent Random Variables

Noga Alon, Oded Goldreich, Johan Håstad et al. · Random Structures and Algorithms · 1992 · 569 citations

, , +8