Self-testing/correcting with applications to numerical problems

The Design and Analysis of Computer Algorithms

Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403

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

Gaussian elimination is not optimal

Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509

Approximate formulas for some functions of prime numbers

Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,596

How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

Blum, M., & Micali, S. M. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,309

Schnelle Multiplikation großer Zahlen

Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107

Trading group theory for randomness

Babai, L. (1985) · doi:10.1145/22145.22192 · Cited by 781

Multi-prover interactive proofs: how to remove intractability

Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/62212.62223 · Cited by 471

Monte-Carlo approximation algorithms for enumeration problems

Karp, R. M., Luby, M. G., & Madras, N. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90038-2 · Cited by 323

New directions in testing

Lipton, R. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/13 · Cited by 270

Quasi-random words and limits of word sequences

Hàn, H., Kiwi, M. A., & Pavez‐Signé, M. (2021) · European Journal of Combinatorics · doi:10.1016/j.ejc.2021.103403 · Cited by 2

PCL: Packet Classification with Limited Knowledge

Demianiuk, V., Hajaj, C., & Kogan, K. (2021) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom42981.2021.9488751 · Cited by 2

A Canonical Form for Testing Boolean Function Properties

Dachman-Soled, D., & Servedio, R. A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22935-0_39 · Cited by 2

Testing Formula Satisfaction

Fischer, E., Goldhirsh, Y., & Lachish, O. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31155-0_33 · Cited by 2

Post-mortem black-box correctness tests for basic parallel data structures

Gibbons, P. B., Bruno, J. L., & Phillips, S. (1999) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/305619.305625 · Cited by 2

A Property Tester for Tree-Likeness of Quartet Topologies

Chang, M., Lin, C.-C., & Rossmanith, P. (2010) · Theory of Computing Systems · doi:10.1007/s00224-010-9276-5 · Cited by 2

Testable and untestable classes of first-order formulae

Jordan, C., & Zeugmann, T. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2012.01.007 · Cited by 2

Approximate modularity revisited

Feige, U., Feldman, M., & Talgam-Cohen, I. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055476 · Cited by 2

The Cube Attack on Courtois Toy Cipher

Szmidt, J. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-76620-1_14 · Cited by 2

Local Testing of Lattices

Chandrasekaran, K., Cheraghchi, M., Gandikota, V., & Grigorescu, E. (2018) · SIAM Journal on Discrete Mathematics · doi:10.1137/17m1110353 · Cited by 2

Agreement Tests on Graphs and Hypergraphs

Dinur, I., Filmus, Y., & Harsha, P. (2025) · SIAM Journal on Computing · doi:10.1137/21m1397684 · Cited by 2

Quantum and Randomised Algorithms for Non-linearity Estimation

Bera, D., & Sapv, T. (2021) · ACM Transactions on Quantum Computing · doi:10.1145/3456509 · Cited by 2

Analyzing boolean functions on the biased hypercube via higher-dimensional agreement tests

Dinur, I., Filmus, Y., & Harsha, P. (2019) · Symposium on Discrete Algorithms · doi:10.5555/3310435.3310563 · Cited by 2

The complexity of modular graph automorphism

Arvind, V., Beigel, R., & Lozano, A. (1998) · Lecture notes in computer science · doi:10.1007/bfb0028559 · Cited by 2

On quantum computation theory

van Dam, W. K. (2002) · Cited by 2

Testing Linear Properties: Some general themes

Sudan, M. (2011) · Cited by 2

Local Hamiltonians with No Low-energy Trivial StatesPreprint

Eldar, L., & Harrow, A. W. (2015) · arXiv (Cornell University) · Cited by 2

New Approaches for Secure Outsourcing Algorithm for Modular Exponentiations.Preprint

Lin, X., Sun, L., Qu, H., & Zhang, X. (2016) · IACR Cryptology ePrint Archive · Cited by 2

New bounds for Szemerédi's theorem, III: A polylogarithmic bound for $r_4(N)$Preprint

Green, B., & Tao, T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.01703 · Cited by 2

High Dimensional Expanders and Property TestingPreprint

Kaufman, T., & Lubotzky, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.2367 · Cited by 2

Near-Linear Regimes for One-Sided Distribution-Free Junta TestingPreprint

Zhang, X. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.10833 · Cited by 2

Topological reconstruction theorems for varietiesPreprint

Kollár, J., Lieblich, M., Olsson, M., & Sawin, W. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2003.04847 · Cited by 2

Probabilistic Proof Systems

Goldreich, O. (1994) · BRICS Report Series · doi:10.7146/brics.v1i28.21643 · Cited by 2

Languages that are Recognized by Simple Counter Automata are not necessarily TestablePreprint

Lachish, O., & Newman, I. (2005) · Electronic colloquium on computational complexity · Cited by 2

Codes with locality : constructions and applications to cryptographic protocols

Lavauzelle, J. (2018) · doi:10.70675/30e2ea2cz3cc5z4819zb918zf8338041000d · Cited by 2

Self-correcting for function fields of finite transcendental degree

Blum, M., Codenotti, B., Gemmell, P. S., & Shahoumian, T. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60084-1_104 · Cited by 2

A High Dimensional Goldreich-Levin Theorem

Newton, P., Richelson, S., & Wilson, C. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585224 · Cited by 1

Improved Optimal Testing Results from Global Hypercontractivity

Kaufman, T., & Minzer, D. (2025) · SIAM Journal on Computing · doi:10.1137/23m1571022 · Cited by 1

The Fault Tolerance of NP-Hard Problems

Glaßer, C., Pavan, A., & Travers, S. D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00982-2_32 · Cited by 1

Probabilistic Verification and Non-Approximability

Szegedy, M. (2006) · Kluwer Academic Publishers eBooks · doi:10.1007/0-387-23830-1_3 · Cited by 1

Hard Functions for Low-Degree Polynomials over Prime Fields

Bogdanov, A., Kawachi, A., & Tanaka, H. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22993-0_14 · Cited by 1

A New View on Worst-Case to Average-Case Reductions for NP Problems

Holenstein, T., & Künzler, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-08783-2_18 · Cited by 1

Testing algebraic geometric codes

Chen, H. (2009) · Science in China Series A Mathematics · doi:10.1007/s11425-009-0141-4 · Cited by 1

Correlation Testing for Affine Invariant Properties on $\mathbb{F}_p^n$ in the High Error Regime

Hatami, H., & Lovett, S. (2014) · SIAM Journal on Computing · doi:10.1137/110831349 · Cited by 1

On-line approximate string matching with bounded errors

Kiwi, M. A., Navarro, G., & Telha, C. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2011.08.005 · Cited by 1

Green’s Conjecture and Testing Linear Invariant Properties

Shapira, A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_30 · Cited by 1

On Being Far from Far and on Dual Problems in Property Testing

Tell, R. (2016) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2840728.2840732 · Cited by 1

О коэффициентах аддитивности и аффинности дискретных функций

Глухов, М. М., & Закревский, П. Н. (2012) · Дискретная математика · doi:10.4213/dm1170 · Cited by 1

Modern Cryptography, Probabilistic Proofs and Pseudorandomness (Second Edition - author's copy)

Goldreich, O. (2000) · Cited by 1

Testing Read-Once Formula Satisfaction

Fischer, E., Goldhirsh, Y., & Lachish, O. (2016) · ACM Transactions on Computation Theory · doi:10.1145/2897184 · Cited by 1

Testing properties of functions on finite groups

Oono, K., & Yoshida, Y. (2016) · Random Structures and Algorithms · doi:10.1002/rsa.20639 · Cited by 1

Reducing Testing Affine Spaces to Testing Linearity of Functions

Goldreich, O. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-43662-9_13 · Cited by 1

One-Sided Error Testing of Monomials and Affine Subspaces

Goldreich, O., & Ron, D. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-88946-2_22 · Cited by 1

Testing Linearity against Non-signaling Strategies

Chiesa, A., Manohar, P., & Shinkar, I. (2020) · ACM Transactions on Computation Theory · doi:10.1145/3397474 · Cited by 1

On Testability of First-Order Properties in Bounded-Degree Graphs and Connections to Proximity-Oblivious Testing

Adler, I., Köhler, N., & Peng, P. (2024) · SIAM Journal on Computing · doi:10.1137/23m1556253 · Cited by 1

On one-sided testing affine subspaces

Bshouty, N. H. (2024) · Theoretical Computer Science · doi:10.1016/j.tcs.2024.114745 · Cited by 1

Error-Tolerant Side-Channel Cube Attack Revisited

Li, Z., Zhang, B., Roy, A., & Fan, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-13051-4_16 · Cited by 1

Locally testable codes and cayley graphs

Gopalan, P., Vadhan, S., & Zhou, Y. (2014) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2554797.2554807 · Cited by 1

Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs

Bhattacharyya, A., & Gopi, S. (2017) · ACM Transactions on Computation Theory · doi:10.1145/3016802 · Cited by 1

Property Testing in Computational Geometry (Extended Abstract)

Czumaj, A., Sohler, C., & Ziegler, M. (2000) · Cited by 1

Random Walks and Rapid Mixing

Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0012 · Cited by 1

Improved bounds for testing Dyck languages

Fischer, E., Magniez, F., & Starikovskaya, T. (2018) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975031.100 · Cited by 1

Lecture 5: Derandomization (Part II)

Harsha, P., & Barth, A. (2005) · Cited by 1

Approximate Modularity Revisited

Feige, U., Feldman, M., & Talgam-Cohen, I. (2020) · SIAM Journal on Computing · doi:10.1137/18m1173873 · Cited by 1

Testing noisy linear functions for sparsity

Chen, X., De, A., & Servedio, R. A. (2020) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3357713.3384239 · Cited by 1

Untestable Properties Expressible with Four First-Order Quantifiers

Jordan, C., & Zeugmann, T. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13089-2_28 · Cited by 1

On probabilistic proof systems and hardness of approximation

Holmerin, J. (2002) · Cited by 1

Lower Bounds on Testing Functions of Low Fourier DegreePreprint

Hatami, P. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.3479 · Cited by 1

Dimensionnement et intégration d'un chiffre symétrique dans le contexte d'un système d'information distribué de grande taille

Roche, T. (2010) · HAL · Cited by 1

On the Work of Madhu Sudan

Wigderson, A. (2003) · Mitteilungen der Deutschen Mathematiker-Vereinigung · doi:10.1515/dmvm-2003-0027 · Cited by 1

Testing k-wise Independent Distributions

Xie, N. (2012) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 1

Candidate Lasserre Integrality Gap For Unique Games.Preprint

Khot, S., & Moshkovitz, D. (2014) · Electronic colloquium on computational complexity · Cited by 1

Local Testing for Membership in LatticesPreprint

Chandrasekaran, K., Cheraghchi, M., Gandikota, V., & Grigorescu, E. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1608.00180 · Cited by 1

Optimization and Approximation

Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0009 · Cited by 1

Tolerant Versus Intolerant Testing for Boolean Properties

Fischer, E., & Fortnow, L. (2004) · Cited by 1

Linearity and Group Homomorphism Testing/Testing Hadamard Codes

Raskhodnikova, S., & Rubinfeld, R. (2015) · Encyclopedia of Algorithms · doi:10.1007/978-3-642-27848-8_202-2 · Cited by 1

The Query Complexity of Program Checking by Constant-Depth Circuits

Arvind, V., Subrahmanyam, K. V., & Vinodchandran, N. V. (1999) · Lecture notes in computer science · doi:10.1007/3-540-46632-0_13 · Cited by 1

The Cube Attack on Stream Cipher Trivium and Quadraticity Tests.

Mroczkowski, P., & Szmidt, J. (2010) · Cited by 1

Settling the query complexity of non-adaptive junta testingPreprint

Chen, X., Servedio, R. A., Tan, L.-Y., Waingarten, E., & Xie, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.06314 · Cited by 1

Low-degree tests at large distancesPreprint

Samorodnitsky, A. (2006) · arXiv (Cornell University) · Cited by 1

Distribution-Free Testing of Linear Functions on R^nPreprint

Fleming, N., & Yoshida, Y. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.03391 · Cited by 1

Reduction From Non-Unique Games To Boolean Unique GamesPreprint

Eldan, R., & Moshkovitz, D. (2020) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2022.64 · Cited by 1

Toward Probabilistic Checking against Non-Signaling Strategies with Constant LocalityPreprint

Jahanara, M. M., Koroth, S., & Shinkar, I. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.04892 · Cited by 1

Chapter 8 Notes and References

Lőrinczi, J., Hiroshima, F., & Betz, V. (2011) · De Gruyter eBooks · doi:10.1515/9783110203738.455 · Cited by 1

Techniques of cryptanalysis for symmetric-key primitives

Coggia, D. (2021) · theses.fr (ABES) · doi:10.70675/67238cdfz59acz45c7zb136zc4ae1bf77739 · Cited by 1

Locally Testable Codes

Harsha, P. (2015) · Encyclopedia of Algorithms · doi:10.1007/978-3-642-27848-8_707-1

Optimal bounds for monotonicity and Lipschitz testing over the hypercubePreprint

Chakrabarty, D., & Seshadhri, C. (2012) · arXiv (Cornell University)

Property Testing for Cyclic Groups and Beyond

Gall, F. L., & Yoshida, Y. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22685-4_38

How close can we come to a parity function when there isn't one?Preprint

Moore, C., & Russell, A. C. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.4897

On the Semantics of Local Characterizations for Linear-Invariant Properties

Bhatttacharyya, A., Grigorescu, E., Nordström, J., & Xie, N. (2011)

Derandomizing Graph Tests for Homomorphism

Li, A., & Tang, L. (2008) · Springer eBooks · doi:10.1007/978-3-540-79228-4_9

Tight lower bounds for adaptive linearity tests

Lovett, S. (2007)

Local Graph Exploration and Fast Property Testing

Czumaj, A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15775-2_35

A Hypergraph Dictatorship Test with Perfect CompletenessPreprint

Chen, V. (2008) · doi:10.48550/arxiv.0811.1922

Local Property Reconstruction and Monotonicity

Saks, M., & Seshadhri, C. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_29

Complexity Upper Bounds for Classical Locally Random Reductions Using a Quantum Computational Argument

Tripathi, R. S. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74456-6_49

Some Recent Results on Local Testing of Sparse Linear Codes

Kopparty, S., & Saraf, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_26

Error correcting codes: local testing, list decoding, and applications

Zuckerman, D., & Patthak, A. C. (2007)

Checker for data structures which sort elements

Wierzbowska, I. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00167-1

Characterizations of locally testable linear- and affine-invariant families

Li, A., & Pan, Y. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2011.09.030

On the derandomization of the graph test for homomorphism over groups

Tang, L. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.12.046

Hard Functions for Low-Degree Polynomials over Prime Fields

Bogdanov, A., Kawachi, A., & Tanaka, H. (2013) · ACM Transactions on Computation Theory · doi:10.1145/2493246.2493248

TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS

Yahalom, O. (2012) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054112500219

Testing consistency of quartet topologies: A parameterized approach

Chang, M., Lin, C.-C., & Rossmanith, P. (2013) · Information Processing Letters · doi:10.1016/j.ipl.2013.08.006

Local computation in codes

Kaufman, T. (2010) · IEEE Information Theory Workshop (ITW) · doi:10.1109/cig.2010.5592932

SIGACT news complexity theory column 63

Hemaspaandra, L. A. (2009) · ACM SIGACT News · doi:10.1145/1556154.1556169

Guaranteed Slowdown, Generalized Encryption Scheme, and Function Sharing

Lifshits, Y. (2006)

On the Query Complexity of Testing for Eulerian Orientations

Fischer, E. O., Matsliah, A., Newman, I., & Yahalom, O. (2009)

A nonadaptive NC checker for permutation group intersection

Arvind, V., & Torán, J. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1997.612316

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness

Devadas, S., & Rubinfeld, R. (2015) · Theory of Computing Systems · doi:10.1007/s00224-015-9639-z

A Guide to Self-Testing/Correcting Pairs: Everything you ever wanted to know and more

(2003)

A mathematical theory of self-checking, self-testing and self-correcting programs

Rubinfeld, R. (1991) · Cited by 53

Self-testing/correcting for polynomials and for approximate functions

Gemmell, P. S., Lipton, R., Rubinfeld, R., Sudan, M., & Wigderson, A. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103429 · Cited by 184

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

Kiwi, M. A., Magniez, F., & Sántha, M. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45878-6_2 · Cited by 21

Testing multivariate linear functions

Ergün, F. (1995) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/225058.225167 · Cited by 11