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

Short Locally Testable Codes and Proofs: A Survey in Two Parts

Goldreich, O. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_6 · Cited by 22

Pipelined algorithms to detect cheating in long-term grid computations

Goodrich, M. T. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.08.008 · Cited by 22

High-rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Kopparty, S., Meir, O., Ron‐Zewi, N., & Saraf, S. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897523 · Cited by 22

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

Fast approximate PCPs

Ergün, F., Kumar, R., & Rubinfeld, R. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301267 · Cited by 22

Testing of function that have small width branching programs

Newman, I. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892112 · Cited by 22

Testing and Spot-Checking of Data Streams

Feigenbaum, Kannan, Strauss, & Viswanathan, V. (2002) · Algorithmica · doi:10.1007/s00453-002-0959-4 · Cited by 22

Power from random strings

Allender, E., Buhrman, H., Koucký, M., van Melkebeek, D., & Ronneburger, D. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181992 · Cited by 22

Some Applications of Coding Theory in Computational ComplexityPreprint

Trevisan, L. (2004) · arXiv (Cornell University) · Cited by 22

NEW BOUNDS FOR SZEMERÉDI'S THEOREM, III: A POLYLOGARITHMIC BOUND FOR

Green, B., & Tao, T. (2017) · Mathematika · doi:10.1112/s0025579317000316 · Cited by 21

Composition of Semi-LTCs by Two-Wise Tensor Products

Ben‐Sasson, E., & Viderman, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_29 · Cited by 21

Testing monotonicity over graph products

Halevy, S., & Eyal Kushilevitz, Z. (2008) · Random Structures and Algorithms · doi:10.1002/rsa.20211 · Cited by 21

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

On the Structure of Boolean Functions with Small Spectral Norm

Shpilka, A., Tal, A., & Volk, B. L. (2015) · Computational Complexity · doi:10.1007/s00037-015-0110-y · Cited by 20

An Improved Algorithm for Secure Outsourcing of Modular Exponentiations

Ye, J., Chen, X., & Ma, J. (2015) · International Conference on Advanced Information Networking and Applications Workshops (WAINA) · doi:10.1109/waina.2015.34 · Cited by 20

Three-Player Entangled XOR Games are NP-Hard to Approximate

Vidick, T. (2016) · SIAM Journal on Computing · doi:10.1137/140956622 · Cited by 59

Testing Hypergraph Coloring

Czumaj, A., & Sohler, C. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_41 · Cited by 20

A discussion of practices for enhancing diversity in software designs

Strigini, L., & Bev Littlewood, A. (2000) · City Research Online (City University London) · Cited by 20

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

New Extension of the Weil Bound for Character Sums with Applications to Coding

Kaufman, T., & Lovett, S. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.41 · Cited by 19

Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

Ben-Or, M., Coppersmith, D., Luby, M., & Rubinfeld, R. (2007) · Random Structures and Algorithms · doi:10.1002/rsa.20182 · Cited by 19

Observing biases in the state: case studies with Trivium and Trivia-SC

Sarkar, S., Maitra, S., & Baksi, A. (2016) · Designs Codes and Cryptography · doi:10.1007/s10623-016-0211-x · Cited by 19

Fast distributed algorithms for testing graph properties

Censor-Hillel, K., Fischer, E., Schwartzman, G., & Vasudev, Y. (2018) · Distributed Computing · doi:10.1007/s00446-018-0324-8 · Cited by 19

New Results on Quantum Property Testing

Chakraborty, S., Fischer, E., Matsliah, A., & de Wolf, R. (2010) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.fsttcs.2010.145 · Cited by 19

On Sample-Based Testers

Goldreich, O., & Ron, D. (2015) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2688073.2688080 · Cited by 19

Program result checking: A new approach to making programs more reliable

Blum, M. (1993) · Lecture notes in computer science · doi:10.1007/3-540-56939-1_57 · Cited by 19

Locally Testable Cyclic Codes

Babai, L., Shpilka, A., & Štefankovič, D. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.851735 · Cited by 19

Testing 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

Using Program Checking to Ensure the Correctness of Compiler Implementations

Glesner, S. (2003) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.3217/jucs-009-03-0191 · Cited by 21

Locality and Checkability in Wait-Free Computing

Fraigniaud, P., Rajsbaum, S., & Travers, C. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-24100-0_34 · Cited by 18

Local Correctability of Expander Codes

Hemenway, B., Ostrovsky, R., & Wootters, M. K. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-39206-1_46 · Cited by 18

Testing surface area with arbitrary accuracy

Neeman, J. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591807 · Cited by 18

Partial 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

Proclaiming Dictators and Juntas or Testing Boolean Formulae

Parnas, M., Ron, D., & Samorodnitsky, A. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44666-4_30 · Cited by 18

Breaking the quadratic barrier for 3-LCC's over the reals

Dvir, Z., Saraf, S., & Wigderson, A. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591818 · Cited by 17

High order differential attacks on stream ciphers

Knellwolf, S., & Meier, W. (2012) · Cryptography and Communications · doi:10.1007/s12095-012-0071-9 · Cited by 17

Candidate hard unique game

Khot, S., & Moshkovitz, D. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897531 · Cited by 17

An adaptivity hierarchy theorem for property testing

Canonne, C. L., & Gur, T. (2018) · Computational Complexity · doi:10.1007/s00037-018-0168-4 · Cited by 17

Making the Best of Cases by Approximation, Interpolation and Extrapolation

Lieber, J., Nauer, E., Prade, H. M., & Richard, G. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-01081-2_38 · Cited by 17

Towards local testability for quantum coding

Leverrier, A., Londe, V., & Zémor, G. (2022) · Quantum · doi:10.22331/q-2022-02-24-661 · Cited by 17

Lower Bounds for Testing Computability by Small Width OBDDs

Brody, J., Matulef, K., & Wu, C. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20877-5_32 · Cited by 17

Guest column

Trevisan, L. (2009) · ACM SIGACT News · doi:10.1145/1556154.1556170 · Cited by 17

On the Power of Randomized Reductions and the Checkability of SAT

Mahmoody, M., & Xiao, D. (2010) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2010.16 · Cited by 17

Property Testing of Regular Tree Languages

Magniez, F., & de Rougemont, M. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27836-8_78 · Cited by 17

From algorithms to working programs: On the use of program checking in LEDA

Mehlhorn, K., & Näher, S. (1998) · Lecture notes in computer science · doi:10.1007/bfb0055759 · Cited by 17

Verified Code Generation for Embedded Systems

Glesner, S., Geiß, R., & Boesler, B. (2002) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)80394-3 · Cited by 17

Nearly complete graphs decomposable into large induced matchings and their applications

Alon, N., Moitra, A., & Benny Sudakov, C. (2013) · Journal of the European Mathematical Society · doi:10.4171/jems/398 · Cited by 16

Recognizing Well-Parenthesized Expressions in the Streaming Model

Magniez, F., Mathieu, C., & Nayak, A. (2014) · SIAM Journal on Computing · doi:10.1137/130926122 · Cited by 16

On the structure of boolean functions with small spectral norm

Shpilka, A., Tal, A., & Volk, B. L. (2014) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2554797.2554803 · Cited by 16

Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs

Bhangale, A., Harsha, P., Paradise, O., & Tal, A. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00084 · Cited by 20

Efficient testing of groups

Friedl, K., Ivanyos, G., & Sántha, M. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060614 · Cited by 16

Symmetric LDPC Codes and Local Testing

Kaufman, T., & Wigderson, A. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_25 · Cited by 16

On Sample-Based Testers

Goldreich, O., & Ron, D. (2016) · ACM Transactions on Computation Theory · doi:10.1145/2898355 · Cited by 16

Tolerant Algorithms

Klein, R., Penninger, R., Sohler, C., & Woodruff, D. P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-23719-5_62 · Cited by 16

Semiautomated Metamorphic Testing Approach for Geographic Information Systems: An Empirical Study

Hui, Z., Huang, S., Chua, C., & Chen, T. Y. (2019) · IEEE Transactions on Reliability · doi:10.1109/tr.2019.2931561 · Cited by 16

A unified framework for testing linear‐invariant properties

Bhattacharyya, A., Grigorescu, E., & Shapira, A. (2013) · Random Structures and Algorithms · doi:10.1002/rsa.20507 · Cited by 16

Testing Monotonicity over Graph Products

Halevy, S., & Eyal Kushilevitz, Z. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27836-8_61 · Cited by 16

Designing Checkers for Programs that Run in Parallel

Rubinfeld, R. (1996) · Algorithmica · doi:10.1007/bf01961540 · Cited by 16

Cube attacks on round-reduced TinyJAMBU

Teng, W. L., Salam, I., Yau, W.-C., Pieprzyk, J., & Phan, R. C.-W. (2022) · Scientific Reports · doi:10.1038/s41598-022-09004-3 · Cited by 15

Stabilizer Testing and Magic Entropy via Quantum Fourier Analysis

Bu, K., Gu, W., & Jaffe, A. M. (2025) · Communications in Mathematical Physics · doi:10.1007/s00220-025-05421-3 · Cited by 37

A Two Prover One Round Game with Strong Soundness

Khot, S., & Safra, M. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.62 · Cited by 15

Pseudo-random Sets in the Grassmann Graph Have Near-Perfect Expansion

Minzer, D. (2022) · ACM eBooks · doi:10.1145/3568031.3568036 · Cited by 15

Derandomizing Homomorphism Testing in General Groups

Shpilka, A., & Wigderson, A. (2006) · SIAM Journal on Computing · doi:10.1137/s009753970444658x · Cited by 15

Testing problems with sub-learning sample complexity

Kearns, M. J., & Ron, D. (1998) · Conference on Learning Theory · doi:10.1145/279943.279996 · Cited by 15

Testing Properties of Constraint-Graphs

Halevy, S., Lachish, O., Newman, I., & Tsur, D. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.31 · Cited by 15

Behavior of Analogical Inference w.r.t. Boolean Functions

Couceiro, M., Hug, N., Prade, H. M., & Richard, G. (2018) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2018/284 · Cited by 15

Testing Low Complexity Affine-Invariant Properties

Bhattacharyya, A., Fischer, E., & Lovett, S. (2013) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611973105.97 · Cited by 15

A Lower Bound for Distribution-Free Monotonicity Testing

Halevy, S., & Eyal Kushilevitz, Z. (2005) · Lecture notes in computer science · doi:10.1007/11538462_28 · Cited by 15

Towards Change Propagating Test Models in Autonomic and Adaptive Systems

Akour, M., Jaidev, A., & King, T. M. (2011) · IEEE International Conference and Workshop on the Engineering of Computer-Based Systems (ECBS) · doi:10.1109/ecbs.2011.23 · Cited by 15

Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates

van Dam, W., Magniez, F., Mosca, M., & Sántha, M. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539702404377 · Cited by 13

Property Testing in Massive Graphs

Goldreich, O. (2002) · Massive computing · doi:10.1007/978-1-4615-0005-6_5 · Cited by 15

Homomorphisms in Graph Property Testing - A SurveyPreprint

Shapira, A., & Alon, N. (2005) · Electronic colloquium on computational complexity · Cited by 15

A Taxonomy of Proof Systems

Goldreich, O. (1997) · Springer eBooks · doi:10.1007/978-1-4612-1872-2_5 · Cited by 15

Introduction to Secure Outsourcing Computation

Chen, X. (2016) · Synthesis lectures on information security, privacy, and trust · doi:10.2200/s00701ed1v01y201602spt016 · Cited by 14

Testing product states, quantum Merlin-Arthur games and tensor optimisation

Harrow, A. W., & Montanaro, A. (2010) · doi:10.48550/arxiv.1001.0017 · Cited by 14

Optimal inapproximability of satisfiable k-LIN over non-abelian groups

Bhangale, A., & Khot, S. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451003 · Cited by 14

More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

Engebretsen, L., & Holmerin, J. (2008) · Random Structures and Algorithms · doi:10.1002/rsa.20226 · Cited by 14

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

Approximate Satisfiability and Equivalence

Fischer, E. O., Magniez, F., & de Rougemont, M. (2006) · ACM/IEEE Symposium on Logic in Computer Science (LICS) · doi:10.1109/lics.2006.12 · Cited by 14

Testing Surface Area

Kothari, P. K., Nayyeri, A., & Wu, C. (2013) · Cited by 14

Settling the Query Complexity of Non-adaptive Junta Testing

Chen, X., Servedio, R. A., Tan, L.-Y., Waingarten, E., & Xie, J. (2018) · Journal of the ACM · doi:10.1145/3213772 · Cited by 14

Property Testing of Regular Tree Languages

Magniez, F., & de Rougemont, M. (2007) · Algorithmica · doi:10.1007/s00453-007-9028-3 · Cited by 14

Finding large 3-free sets I: The small n case

Gasarch, W. I., Glenn, J. R., & Kruskal, C. P. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.06.002 · Cited by 15

Tolerant Versus Intolerant Testing for Boolean Properties

Fischer, E. O., & Fortnow, L. (2005) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2005.30 · Cited by 14

Lecture Notes on Computational Complexity

Trevisan, L. (2004) · Cited by 16

A Brief Introduction to Property Testing

Goldreich, O. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22670-0_31 · Cited by 14

Linear-Consistency Testing

Aumann, Y., Håstad, J., Rabin, M. O., & Sudan, M. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1747 · Cited by 14

A 3-query PCP over integers

Guruswami, V., & Raghavendra, P. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250819 · Cited by 14

Testing hypergraph colorability

Czumaj, A., & Sohler, C. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.09.031 · Cited by 14

Testing st-Connectivity

Chakraborty, S., Fischer, E., Lachish, O., Matsliah, A., & Newman, I. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74208-1_28 · Cited by 13

Testing Linear-Invariant Non-linear Properties: A Short Report

Bhattacharyya, A., Chen, V., Sudan, M., & Xie, N. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_18 · Cited by 13

Improved Side Channel Cube Attacks on PRESENT.

Zhao, X., Wang, T., & Guo, S. (2011) · Cited by 13

Subversion-Resilient Public Key Encryption with Practical Watchdogs

Bemmann, P., Chen, R., & Jager, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-75245-3_23 · Cited by 13

Constant approximating k-clique is w[1]-hard

Lin, B. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451016 · Cited by 13

Testing Juntas: A Brief Survey

Blais, E. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_4 · Cited by 16

Simple analysis of graph tests for linearity and PCP

Håstad, J., & Wigderson, A. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2001.933891 · Cited by 13

NP-hardness of approximately solving linear equations over reals

Khot, S., & Moshkovitz, D. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993692 · Cited by 13

Approximately classic judgement aggregation

Nehama, I. (2013) · Annals of Mathematics and Artificial Intelligence · doi:10.1007/s10472-013-9358-6 · Cited by 13

Direct Sum Testing

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

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