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

On the Randomness Complexity of Property Testing

Goldreich, O., & Sheffet, O. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74208-1_37 · Cited by 6

Distribution-Free Testing Lower Bounds for Basic Boolean Functions

Glasner, D., & Servedio, R. A. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-74208-1_36 · Cited by 6

The Complexity of Entangled Games

Vidick, T. (2011) · eScholarship (California Digital Library) · Cited by 10

Taking Proof based Verified Computation a Few Steps Closer to Practicality (extended version)Preprint

Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A. J., & Walfish, M. (2012) · IACR Cryptology ePrint Archive · Cited by 6

Property Testing of Equivalence under a Permutation Group Action.

Chakraborty, S., & Babai, L. (2008) · Cited by 5

Strong LTCs with Inverse Polylogarithmic Rate and Soundness

Viderman, M. (2013) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2013.34 · Cited by 5

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions

Blocki, J., Cheng, K., Grigorescu, E., Li, X., Zheng, Y., & Zhu, M. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs52979.2021.00077 · Cited by 5

A Survey on Delegated Computation

Crescenzo, G. D., Khodjaeva, M., Kahrobaei, D., & Shpilrain, V. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-05578-2_3 · Cited by 5

Computational Complexity Since 1980

Impagliazzo, R. (2005) · Lecture notes in computer science · doi:10.1007/11590156_2 · Cited by 5

Program Checking with Certificates: Separating Correctness-Critical Code

Glesner, S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45236-2_41 · Cited by 5

$\mathcal{NP}$-Hardness of Approximately Solving Linear Equations over Reals

Khot, S., & Moshkovitz, D. (2013) · SIAM Journal on Computing · doi:10.1137/110846415 · Cited by 5

Testing Lipschitz Functions on Hypergrid Domains

Awasthi, P., Jha, M. K., Molinaro, M., & Raskhodnikova, S. (2015) · Algorithmica · doi:10.1007/s00453-015-9984-y · Cited by 5

The difficulty of testing for isomorphism against a graph that is given in advance

Fischer, E. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007415 · Cited by 5

Breaking the ε-Soundness Bound of the Linearity Test over GF(2)

Kaufman, T., Litsyn, S. N., & Xie, N. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85363-3_39 · Cited by 5

Symmetric LDPC codes and local testing

Kaufman, T., & Wigderson, A. (2015) · COMBINATORICA · doi:10.1007/s00493-014-2715-1 · Cited by 5

Approximate Modularity

Chierichetti, F., Das, A., Dasgupta, A., & Kumar, R. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.74 · Cited by 5

Carries, Group Theory, and Additive Combinatorics

Diaconis, P. W., Shao, X., & Soundararajan, K. (2014) · American Mathematical Monthly · doi:10.4169/amer.math.monthly.121.08.674 · Cited by 5

Three‐query PCPs with perfect completeness over non‐Boolean domains

Engebretsen, L., & Holmerin, J. (2005) · Random Structures and Algorithms · doi:10.1002/rsa.20050 · Cited by 5

Property and Equivalence Testing on Strings

Fischer, E., Magniez, F., & de Rougemont, M. (2004) · Cited by 5

Property Testing via Set-Theoretic OperationsPreprint

Chen, V., Sudan, M., & Xie, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1010.4925 · Cited by 5

Abstract combinatorial programs and efficient property testers

Czumaj, A., & Sohler, C. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181885 · Cited by 5

Nearly Complete Graphs Decomposable into Large Induced Matchings and their ApplicationsPreprint

Alon, N., Moitra, A., & Benny Sudakov, C. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1111.0253 · Cited by 5

Improved Hardness of Approximating k-Clique under ETH

Lin, B., Ren, X., Sun, Y., & Wang, X. (2023) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs57990.2023.00025 · Cited by 4

The Computational Advantage of MIP* Vanishes in the Presence of Noise

Dong, Y., Fu, H., Natarajan, A., Qin, M., Xu, H., & Yao, P. (2025) · Journal of the ACM · doi:10.1145/3760771 · Cited by 12

Stability of homomorphisms, coverings and cocycles I: equivalence

Chapman, M., & Lubotzky, A. (2025) · European Journal of Mathematics · doi:10.1007/s40879-024-00803-8 · Cited by 4

Towards an optimal query efficient PCP?

Khot, S., Safra, M., & Tulsiani, M. (2013) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2422436.2422458 · Cited by 4

Multi-Linearity Self-Testing with Relative Error

Magniez, F. (2004) · Theory of Computing Systems · doi:10.1007/s00224-004-1125-y · Cited by 4

Efficiently Testing Sparse GF(2) Polynomials

Diakonikolas, I., Lee, H. K., Matulef, K., Servedio, R. A., & Wan, A. (2010) · Algorithmica · doi:10.1007/s00453-010-9426-9 · Cited by 4

Cube Attack on Reduced-Round Quavium

Zhang, S., Chen, G., & Li, J. (2015) · International Conference on Mechatronics and Industrial Informatics (ICMII) · doi:10.2991/icmii-15.2015.25 · Cited by 4

New Publicly Verifiable Databases Supporting Insertion Operation

Miao, M., Wang, J., & Ma, J. (2015) · International Conference on Network-Based Information Systems · doi:10.1109/nbis.2015.95 · Cited by 4

Distribution-free Junta Testing

Liu, Z., Chen, X., Servedio, R. A., Sheng, Y., & Xie, J. (2018) · ACM Transactions on Algorithms · doi:10.1145/3264434 · Cited by 4

Rigid Matrices from Rectangular PCPs

Bhangale, A., Harsha, P., Paradise, O., & Tal, A. (2024) · SIAM Journal on Computing · doi:10.1137/22m1495597 · Cited by 4

The fault tolerance of NP-hard problems

Glaßer, C., Pavan, A., & Travers, S. D. (2010) · Information and Computation · doi:10.1016/j.ic.2010.11.012 · Cited by 4

Self-test framework for self-adaptive software architecture

Roopa, Y. M., & Babu, M. R. (2017) · International Conference on Electronics, Communication and Aerospace Technology (ICECA) · doi:10.1109/iceca.2017.8212749 · Cited by 4

Higher-order Fourier Analysis and Applications

Hatami, H., Hatami, P., & Lovett, S. (2019) · now publishers, Inc. eBooks · doi:10.1561/9781680835939 · Cited by 4

Efficient and Secure Delegation of Exponentiation in General Groups to a Single Malicious Server

Crescenzo, G. D., Khodjaeva, M., Kahrobaei, D., & Shpilrain, V. (2020) · Mathematics in Computer Science · doi:10.1007/s11786-020-00462-4 · Cited by 4

Hardness Self-Amplification from Feasible Hard-Core Sets

Hirahara, S., & Shimizu, N. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00058 · Cited by 4

A Hypergraph Dictatorship Test with Perfect Completeness

Chen, V. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_34 · Cited by 4

A nonadaptive NC checker for permutation group intersection

Arvind, V., & Torán, J. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00159-6 · Cited by 4

Efficient self-testing/self-correction of linear recurrences

Kumar, S. R., & Sivakumar, D. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548519 · Cited by 4

The Gowers norm in the testing of Boolean functions

Chen, V. Y.-W. (2009) · Cited by 4

On the Nonexistence of $q$ -Bent Boolean Functions

Klapper, A., & Chen, Z. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2758788 · Cited by 4

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

Goldreich, O. (2019) · Computational Complexity · doi:10.1007/s00037-019-00187-2 · Cited by 4

Erasures versus errors in local decoding and property testing

Raskhodnikova, S., Ron‐Zewi, N., & Varma, N. M. (2021) · Random Structures and Algorithms · doi:10.1002/rsa.21031 · Cited by 4

SMT‐based cube attack on round‐reduced Simeck32/64

Zaheri, M., & Sadeghiyan, B. (2020) · IET Information Security · doi:10.1049/iet-ifs.2019.0496 · Cited by 4

Cube Attacks on Tweakable Black Box Polynomials.

Dinur, I., & Adi Shamir, Z. (2008) · Cited by 4

Three-query PCPs with perfect completeness over non-Boolean domains

Engebretsen, L., & Holmerin, J. (2004) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2003.1214428 · Cited by 4

Linearity Testing/Testing Hadamard Codes

Rubinfeld, R. (2008) · Encyclopedia of Algorithms · doi:10.1007/978-0-387-30162-4_202 · Cited by 4

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)Preprint

Harsha, P., Charikar, M., Andrews, M., Arora, S., Khot, S., Moshkovitz, D., Zhang, L., Aazami, A., Desai, D., Gorodezky, I., et al. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.3864 · Cited by 4

Local Hamiltonians with Approximation-Robust EntanglementPreprint

Eldar, L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1503.02269 · Cited by 4

Partial Function Extension with Applications to Learning and Property TestingPreprint

Bhaskar, U., & Kumar, G. (2018) · arXiv (Cornell University) · doi:10.4230/lipics.isaac.2020.46 · Cited by 4

Metamorphic Testing and its Application on Hardware Fault-Tolerance

Liu, J. (2011) · Minds at UW (University of Wisconsin) · Cited by 4

Property Testing for Cyclic Groups and BeyondPreprint

Yoshida, G. Y. (2016) · Cited by 4

A Practical Platform for Cube-Attack-like Cryptanalyses.Preprint

Zhu, B. W., Yu, W., & Wang, T. (2010) · IACR Cryptology ePrint Archive · Cited by 4

New perspectives on the complexity of computational learning, and other problems in theoretical computer science

Barak, B., & Xiao, D. (2009) · Cited by 4

On Monotonicity Testing and the 2-to-2 Games Conjecture

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

Multi-linearity Self-Testing with Relative Error

Magniez, F. (2000) · Lecture notes in computer science · doi:10.1007/3-540-46541-3_25 · Cited by 3

Lower bounds for adaptive linearity tests

Lovett, S. (2008) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2008.1313 · Cited by 3

Property testing for cyclic groups and beyond

Gall, F. L., & Yoshida, Y. (2012) · Journal of Combinatorial Optimization · doi:10.1007/s10878-011-9445-8 · Cited by 3

Performance of Concatenated Kernel Code in Cognitive Radio Networks

Kumar, C. P., & Selvakumar, R. (2017) · Procedia Computer Science · doi:10.1016/j.procs.2017.09.142 · Cited by 3

Testing Linear-Invariant Properties

Tidor, J., & Zhao, Y. (2022) · SIAM Journal on Computing · doi:10.1137/21m1397246 · Cited by 3

A quantum algorithm to estimate the Gowers $$U_2$$ norm and linearity testing of Boolean functions

Jothishwaran, C. A., Tkachenko, A., Gangopadhyay, S., Riera, C., & Stănică, P. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02817-z · Cited by 3

High-Dimensional Computational Geometry

Andoni, A. (2016) · Chapman & Hall/CRC eBooks · doi:10.1201/b19567-14 · Cited by 3

Quasi-Random Words and Limits of Word Sequences

Hàn, H., Kiwi, M. A., & Pavez‐Signé, M. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-61792-9_39 · Cited by 3

Untestable Properties in the Kahr-Moore-Wang Class

Jordan, C., & Zeugmann, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20920-8_19 · Cited by 3

Sparse Random Linear Codes are Locally Decodable and Testable

Kaufman, T., & Sudan, M. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.4389528 · Cited by 3

Limitations of Local Filters of Lipschitz and Monotone Functions

Awasthi, P., Jha, M. K., Molinaro, M., & Raskhodnikova, S. (2015) · ACM Transactions on Computation Theory · doi:10.1145/2692372.2692373 · Cited by 3

Finding Significant Fourier Transform Coefficients Deterministically and Locally

Akavia, A. (2008) · Cited by 3

Testing of large number multiplication functions in cryptographic systems

Tse, T. H., Chen, T. Y., & Zhou, Z. Q. (2002) · Asia-Pacific Conference on Quality Software (APAQS) · doi:10.1109/apaq.2000.883782 · Cited by 3

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities

Ron, D., & Servedio, R. A. (2013) · Algorithmica · doi:10.1007/s00453-013-9858-0 · Cited by 3

On coherence, random-self-reducibility, and self-correction

Joan Feigenbaum, A., Fortnow, L., Laplante, S., & Naik, A. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1996.507668 · Cited by 3

Practical ultra‐reliability for abstract data types

Nikolik, B., & Hamlet, D. (2007) · Software Testing Verification and Reliability · doi:10.1002/stvr.367 · Cited by 3

On Hardness of Approximating the Parameterized Clique Problem

Khot, S., & Shinkar, I. (2016) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2840728.2840733 · Cited by 3

Verifiable algorithm for outsourced database with updating

Guo, Z., Li, H., Cao, C., & Wei, Z. (2017) · Cluster Computing · doi:10.1007/s10586-017-1133-8 · Cited by 3

Empirical analysis of algorithms for the shortest negative cost cycle problem

Anderson, M., Williamson, M. D., & Subramani, K. (2018) · Discrete Applied Mathematics · doi:10.1016/j.dam.2018.03.055 · Cited by 3

Quantum cryptographic property testing of multi-output Boolean functions

Jingyi, C., & Guo, J. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2299-1 · Cited by 3

Local decoding and testing of polynomials over grids

Bafna, M., Srinivasan, S., & Sudan, M. (2020) · Random Structures and Algorithms · doi:10.1002/rsa.20933 · Cited by 3

Verifiable Computing Using Computation Fingerprints Within FHE

Dolev, S., & Kalma, A. (2021) · IEEE International Symposium on Network Computing and Applications (NCA) · doi:10.1109/nca53618.2021.9685831 · Cited by 3

Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions

Sălăgean, A., & Stănică, P. (2021) · Cryptography and Communications · doi:10.1007/s12095-021-00529-4 · Cited by 3

Testability of Homomorphism Inadmissibility

Chen, H., & Yoshida, Y. (2019) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3294052.3319679 · Cited by 3

An information-theoretic treatment of random-self-reducibility

Joan Feigenbaum, A., & Strauss, M. J. (1997) · Lecture notes in computer science · doi:10.1007/bfb0023486 · Cited by 3

Some approximations in Model Checking and TestingPreprint

Gaudel, M.-C., Lassaigne, R., Magniez, F., & de Rougemont, M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1304.5199 · Cited by 3

Relational Properties Expressible with One Universal Quantifier Are Testable

Jordan, C., & Zeugmann, T. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04944-6_12 · Cited by 3

Linear Consistency Testing

Aumann, Y., Håstad, J., Rabin, M. O., & Sudan, M. (1999) · Lecture notes in computer science · doi:10.1007/978-3-540-48413-4_11 · Cited by 3

Hardness of Approximately Solving Linear Equations Over Reals.Preprint

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

Property Testing: A Learning Theory Perspective

Ron, D. (2007) · Springer eBooks · doi:10.1007/978-3-540-72927-3_1 · Cited by 3

On-Line Approximate String Matching with Bounded Errors

Kiwi, M. A., Navarro, G., & Telha, C. (2008) · Springer eBooks · doi:10.1007/978-3-540-69068-9_14 · Cited by 3

New Efficient and Flexible Algorithms for Secure Outsourcing of Bilinear Pairings.Preprint

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

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

Tell, R. (2015) · Electronic colloquium on computational complexity · Cited by 3

Almost Optimal Distribution-Free Junta TestingPreprint

Bshouty, N. H. (2019) · arXiv (Cornell University) · doi:10.4230/lipics.ccc.2019.2 · Cited by 3

Separations of Matroid Freeness PropertiesPreprint

Bhattacharyya, A., Grigorescu, E., Nordström, J., & Xie, N. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1008.4401 · Cited by 3

On Learning and Testing Decision TreePreprint

Bshouty, N. H., & Haddad-Zaknoon, C. A. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2108.04587 · Cited by 3

Tolérance aux fautes et reconfiguration dynamique pour les applications distribuées à grande échelle

Besseron, X. (2010) · HAL · Cited by 3

Error-Correction of Matrix Multiplication Algorithms

Hirahara, S., & Shimizu, N. (2025) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3717823.3718244 · Cited by 2

A query efficient non-adaptive long code test with perfect completeness

Tamaki, S., & Yoshida, Y. (2014) · Random Structures and Algorithms · doi:10.1002/rsa.20549 · Cited by 2

Testing graphs against an unknown distribution

Gishboliner, L., & Shapira, A. (2019) · Israel Journal of Mathematics · doi:10.1007/s11856-021-2228-8 · Cited by 2

Concatenated kernel codes

Selvakumar, R., & Kumar, C. P. (2020) · Discrete Mathematics Algorithms and Applications · doi:10.1142/s1793830920500445 · Cited by 2

Simple Local Computation Algorithms for the General Lovász Local Lemma

Achlioptas, D., Gouleakis, T., & Iliopoulos, F. (2020) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/3350755.3400250 · Cited by 2

Low Degree Testing over the Reals

Arora, V., Bhattacharyya, A., Fleming, N., Kelman, E., & Yoshida, Y. (2023) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977554.ch31 · Cited by 2

Parameterized Inapproximability Hypothesis under ETH

Guruswami, V., Lin, B., Ren, X., Sun, Y., & Wu, K. (2025) · Journal of the ACM · doi:10.1145/3749982 · Cited by 2

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