The DOI matches its Crossref record; 103 of the 103 references it cites were found in a registry or an index.
Introduction to Property Testing
Abstract
Property testing is concerned with the design of super-fast algorithms for the structural analysis of large quantities of data. The aim is to unveil global features of the data, such as determining whether the data has a particular property or estimating global parameters. Remarkably, it is possible for decisions to be made by accessing only a small portion of the data. Property testing focuses on properties and parameters that go beyond simple statistics. This book provides an extensive and authoritative introduction to property testing. It provides a wide range of algorithmic techniques for the design and analysis of tests for algebraic properties, properties of Boolean functions, graph properties, and properties of distributions.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Schwartz, J. T. (1980) · Journal of the ACM · doi:10.1145/322217.322225 · Cited by 1,701
An Introduction to Computational Learning Theory
Kearns, M. J., & Vazirani, U. (1994) · doi:10.7551/mitpress/3897.001.0001 · Cited by 1,697
(2005) · Complexity Theory · doi:10.1007/3-540-27477-4_15 · Cited by 1,629
Chor, B., Kushilevitz, E., Goldreich, O., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/293347.293350 · Cited by 1,612
Self-citationData Streams: Algorithms and Applications
Muthukrishnan, S. (2005) · now publishers, Inc. eBooks · doi:10.1561/9781933019604 · Cited by 1,527
Even, S. (1979) · Cited by 1,280
Graph Minors .XIII. The Disjoint Paths Problem
Robertson, N., & Seymour, P. D. (1995) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.1995.1006 · Cited by 1,262
A hard-core predicate for all one-way functions
Goldreich, O., & Levin, L. A. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73010 · Cited by 1,193
Self-citationThe Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,020
Self-citationRaz, R., & Safra, S. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258641 · Cited by 834
On clusterings: Good, bad and spectral
Kannan, R., Vempala, S., & Vetta, A. (2004) · Journal of the ACM · doi:10.1145/990308.990313 · Cited by 834
On the power of unique 2-prover 1-round games
Khot, S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.510017 · Cited by 818
Robust Characterizations of Polynomials with Applications to Program Testing
Rubinfeld, R., & Sudan, M. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539793255151 · Cited by 794
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103428 · Cited by 616
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447372 · Cited by 578
Computational limitations on learning from examples
Pitt, L., & Valiant, L. G. (1988) · Journal of the ACM · doi:10.1145/48014.63140 · Cited by 515
Quick Approximation to Matrices and Applications
Frieze, A., & Kannan, R. (1999) · Combinatorica · doi:10.1007/s004930050052 · Cited by 502
The PCP theorem by gap amplification
Dinur, I. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132553 · Cited by 501
Fast monte-carlo algorithms for finding low-rank approximations
Frieze, A., Kannan, R., & Vempala, S. (2004) · Journal of the ACM · doi:10.1145/1039488.1039494 · Cited by 500
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62223 · Cited by 468
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Computational complexity: a conceptual perspective
(2008) · Choice Reviews Online · doi:10.5860/choice.46-0942 · Cited by 421
Approximating clique is almost NP-complete
Feige, U., Goldwasser, S., Lovasz, L., Safra, S., & Szegedy, M. (2002) · [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science · doi:10.1109/sfcs.1991.185341 · Cited by 396
Efficient probabilistically checkable proofs and applications to approximations
Bellare, M., Goldwasser, S., Lund, C., et al. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167174 · Cited by 317
Property Testing in Bounded Degree Graphs
Goldreich, O., & Ron (2002) · Algorithmica · doi:10.1007/s00453-001-0078-7 · Cited by 309
Self-citationDesigning programs that check their work
Blum, M., & Kanna, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73015 · Cited by 287
Free bits, PCPs and non-approximability-towards tight results
Bellare, M., Goldreich, O., & Sudan, M. (2002) · Proceedings of IEEE 36th Annual Foundations of Computer Science · doi:10.1109/sfcs.1995.492573 · Cited by 265
Self-citationOn the efficiency of local decoding procedures for error-correcting codes
Katz, J., & Trevisan, L. (2000) · Proceedings of the thirty-second annual ACM symposium on Theory of computing · doi:10.1145/335305.335315 · Cited by 264
3-Query Locally Decodable Codes of Subexponential Length
Efremenko, K. (2012) · SIAM Journal on Computing · doi:10.1137/090772721 · Cited by 256
Testing that distributions are close
Batu, T., Fortnow, L., Rubinfeld, R., Smith, W. D., & White, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892113 · Cited by 247
A subexponential algorithm for the discrete logarithm problem with applications to cryptography
Adleman, L. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.2 · Cited by 242
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539705446810 · Cited by 234
Self-citationValiant, G., & Valiant, P. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993727 · Cited by 233
The importance of being biased
Dinur, I., & Safra, S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509915 · Cited by 212
A Coincidence-Based Test for Uniformity Given Very Sparsely Sampled Discrete Data
Paninski, L. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.928987 · Cited by 208
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Kerenidis, I., & de Wolf, R. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780560 · Cited by 194
Short PCPs with Polylog Query Complexity
Ben‐Sasson, E., & Sudan, M. (2008) · SIAM Journal on Computing · doi:10.1137/050646445 · Cited by 194
On the power of two-point based sampling
Chor, B., & Goldreich, O. (1989) · Journal of Complexity · doi:10.1016/0885-064x(89)90015-0 · Cited by 191
Self-citationNearly-linear size holographic proofs
Polishchuk, A., & Spielman, D. A. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195132 · Cited by 191
Nondeterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (2002) · Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89520 · Cited by 188
Two Query PCP with Sub-Constant Error
Moshkovitz, D., & Raz, R. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.60 · Cited by 186
On the power of multi-prover interactive protocols
Fortnow, L., Rompel, J., & Sipser, M. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90251-8 · Cited by 185
Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., & Samorodnitsky, A. (2000) · COMBINATORICA · doi:10.1007/s004930070011 · Cited by 180
Self-citationAlgorithmic and Analysis Techniques in Property Testing
Ron, D. (2010) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000029 · Cited by 179
Conductance and convergence of Markov chains-a combinatorial treatment of expanders
Mihail, M. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63529 · Cited by 175
Linearity testing in characteristic two
Mihir Bellare, Y., Coppersmith, D., Håstad, J., Kiwi, M. A., & Sudan, M. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556674 · Cited by 172
Linear zero-knowledge---a note on efficient zero-knowledge proofs and arguments
Cramer, R., & Damgård, I. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258635 · Cited by 170
The regularity lemma and approximation schemes for dense problems
Frieze, A., & Kannan, R. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548459 · Cited by 170
Constant-round interactive proofs for delegating computation
Reingold, O., Rothblum, G. N., & Rothblum, R. D. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897652 · Cited by 166
Improved Low-Degree Testing and its Applications
Arora, S., & Sudan, M. (2003) · COMBINATORICA · doi:10.1007/s00493-003-0025-0 · Cited by 164
A new proof of the graph removal lemma
Fox, J. (2011) · Annals of Mathematics · doi:10.4007/annals.2011.174.1.17 · Cited by 159
Locally testable codes and PCPs of almost-linear length
Goldreich, O., & Sudan, M. (2006) · Journal of the ACM · doi:10.1145/1162349.1162351 · Cited by 152
Self-citationRandomness-efficient low degree tests and short PCPs via epsilon-biased sets
Ben‐Sasson, E., Sudan, M., Vadhan, S., & Wigderson, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780631 · Cited by 140
Every minor-closed property of sparse graphs is testable
Benjamini, I., Schramm, O., & Shapira, A. (2008) · Advances in Mathematics · doi:10.1016/j.aim.2009.10.018 · Cited by 132
Property Testing: A Learning Theory Perspective
Ron, D. (2008) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000004 · Cited by 132
Property Testing Lower Bounds via Communication Complexity
Blais, E., Brody, J., & Matulef, K. (2012) · Computational Complexity · doi:10.1007/s00037-012-0040-x · Cited by 131
Short PCPs Verifiable in Polylogarithmic Time
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2005) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2005.27 · Cited by 128
Self-citationTesting Basic Boolean Formulae
Parnas, M., Ron, D., & Samorodnitsky, A. (2002) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101407444 · Cited by 108
One-way functions and pseudorandom generators
Levin, L. A. (1985) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/22145.22185 · Cited by 106
Testing Low-Degree Polynomials over GF(2)
Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S. N., & Ron, D. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45198-3_17 · Cited by 102
The Complexity of Approximating the Entropy
Batu, T., Dasgupta, S., Kumar, R., & Rubinfeld, R. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702403645 · Cited by 102
A combinatorial characterization of the testable graph properties
Alon, N., Fischer, E., Newman, I., & Shapira, A. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132555 · Cited by 100
On interactive proofs with a laconic prover
Goldreich, O., Vadhan, S., & Wigderson, A. (2002) · Computational Complexity · doi:10.1007/s00037-002-0169-0 · Cited by 97
Self-citationA lower bound for testing 3-colorability in bounded-degree graphs
Bogdanov, A., Obata, K., & Trevisan, L. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181886 · Cited by 92
Optimal Testing of Reed-Muller Codes
Bhattacharyya, A., Kopparty, S., Schoenebeck, G. R., Sudan, M., & Zuckerman, D. (2010) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.54 · Cited by 81
A sublinear algorithm for weakly approximating edit distance
Batu, T., Ergün, F., Kilian, J., Magen, A., Raskhodnikova, S., Rubinfeld, R., & Rahul Sami, D. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780590 · Cited by 78
Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
Chakrabarty, D., & Seshadhri, C. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488661 · Cited by 71
A New Conceptual Clustering Framework
Mishra, N., Ron, D., & Swaminathan, R. (2004) · Machine Learning · doi:10.1023/b:mach.0000033117.77257.41 · Cited by 69
A Characterization of the (natural) Graph Properties Testable with One-Sided Error
Alon, N., & Shapira, A. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.5 · Cited by 67
Testing for Concise Representations
Diakonikolas, I., Lee, H., Matule, K., Onak, K., Rubinfeld, R., Servedio, R. A., & Wan, A. (2007) · Cited by 67
A divide-and-merge methodology for clustering
Cheng, D., Vempala, S., Kannan, R., & Wang, G. J. (2005) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1065167.1065192 · Cited by 61
Balcan, M.-F., Blais, E., Blum, A. L., & Yang, L. F. (2012) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.64 · Cited by 60
Alon, N., Dar, S., Parnas, M., & Ron, D. (2003) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480102410973 · Cited by 58
Ergün, F., Kannan, S., Kumar, S. R., Rubinfeld, R., & Viswanathan, M. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276757 · Cited by 58
Testing probability distributions using conditional samplesPreprint
Ron, D., & Servedio, R. A. (n.d.) · Cited by 57
Combinatorial Construction of Locally Testable Codes
Meir, O. (2008) · SIAM Journal on Computing · doi:10.1137/080729967 · Cited by 56
Instance optimal learning of discrete distributions
Valiant, G. J., & Valiant, P. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897641 · Cited by 50
Local Monotonicity Reconstruction
Saks, M., & Seshadhri, C. (2010) · SIAM Journal on Computing · doi:10.1137/080728561 · Cited by 48
Testing Membership in Languages that Have Small Width Branching Programs
Newman, I. (2002) · SIAM Journal on Computing · doi:10.1137/s009753970038211x · Cited by 46
Self-testing polynomial functions efficiently and over rational domains
Rubinfeld, R., & Sudan, M. (1992) · Cited by 42
Fast-Match: Fast Affine Template Matching
Korman, S., Reichman, D., Tsur, G., & Avidan, S. (2016) · International Journal of Computer Vision · doi:10.1007/s11263-016-0926-1 · Cited by 42
Testing versus estimation of graph properties
Fischer, E., & Newman, I. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060612 · Cited by 41
Seshadhri, C., & Vondrák, J. (2012) · Algorithmica · doi:10.1007/s00453-012-9719-2 · Cited by 35
A separation theorem in property testing
Alon, N., & Shapira, A. (2008) · COMBINATORICA · doi:10.1007/s00493-008-2321-1 · Cited by 34
Distribution-Free Property Testing
Halevy, S., & Kushilevitz, E. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45198-3_26 · Cited by 33
Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)
Kaufman, T., Litsyn, S. N., & Xie, N. (2010) · SIAM Journal on Computing · doi:10.1137/080715548 · Cited by 29
Hierarchy Theorems for Property Testing
Goldreich, O., Krivelevich, M., Newman, I., & Rozenberg, E. (2011) · Computational Complexity · doi:10.1007/s00037-011-0022-4 · Cited by 22
Self-citationErgün, F., Kumar, R., & Rubinfeld, R. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301267 · Cited by 22
Goldreich, O., & Ron, D. (2015) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2688073.2688080 · Cited by 22
Self-citationTesting Acyclicity of Directed Graphs in Sublinear Time
Bender, M. A., & Ron, D. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45022-x_68 · Cited by 19
Proximity Oblivious Testing and the Role of Invariances
Goldreich, O., & Kaufman, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22935-0_49 · Cited by 19
Self-citationPartial tests, universal tests and decomposability
Fischer, E., Goldhirsh, Y., & Lachish, O. (2014) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2554797.2554841 · Cited by 18
Derandomizing Homomorphism Testing in General Groups
Shpilka, A., & Wigderson, A. (2006) · SIAM Journal on Computing · doi:10.1137/s009753970444658x · Cited by 15
Strong LTCs with Inverse Poly-Log Rate and Constant Soundness
Viderman, M. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.43 · Cited by 14
David, R., Dinur, I., Goldenberg, E., Kindler, G., & Shinkar, I. (2015) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2688073.2688078 · Cited by 13
Algorithmic approaches to statistical questions
Papadimitriou, C. H., & Valiant, G. J. (2012) · Cited by 12
Fischer, E., & Matsliah, A. (2006) · Symposium on Discrete Algorithms · doi:10.5555/1109557.1109591 · Cited by 8
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Computational advantage of quantum random sampling
Hangleiter, D., & Eisert, J. (2023) · Reviews of Modern Physics · doi:10.1103/revmodphys.95.035001 · Cited by 145
Biwhitening Reveals the Rank of a Count Matrix
Landa, B., Zhang, T. T. C. K., & Kluger, Y. (2022) · SIAM Journal on Mathematics of Data Science · doi:10.1137/21m1456807 · Cited by 20
Metadata
- Authors
- Goldreich, O.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2017-11-13
- OpenAlex
- W2769478807
- Cited by
- 270
- References
- 103
- FWCI
- 8.86
- Type
- book
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.