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

Interpreting Deep-Learned Error-Correcting Codes

Devroye, N., Mohammadi, N., Mulgund, A. P., Naik, H., Shekhar, R., Turán, G., Wei, Y., & Žefran, M. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834599 · Cited by 12

Locally testable cyclic codes

Babai, L., Shpilka, A., & Štefankovič, D. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238186 · Cited by 13

Quantum Testers for Hidden Group Properties

Friedl, K., Magniez, F., Sántha, M., & Sen, P. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45138-9_36 · Cited by 13

Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups

Moore, C., & Russell, A. C. (2015) · SIAM Journal on Discrete Mathematics · doi:10.1137/140958578 · Cited by 12

Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions

Chen, X., & Xie, J. (2015) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974331.ch5 · Cited by 12

A Combination of Testability and Decodability by Tensor Products

Viderman, M. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32512-0_55 · Cited by 12

Metamorphic Testing Integer Overflow Faults of Mission Critical Program: A Case Study

Hui, Z., Huang, S., Ren, Z., & Yao, Y. (2013) · Mathematical Problems in Engineering · doi:10.1155/2013/381389 · Cited by 12

Algorithmic approaches to statistical questions

Papadimitriou, C. H., & Valiant, G. J. (2012) · Cited by 12

Homomorphisms in Graph Property Testing

Alon, N., & Shapira, A. (2007) · Springer eBooks · doi:10.1007/3-540-33700-8_17 · Cited by 12

How NP got a new definition: a survey of probabilistically checkable proofsPreprint

Arora, S. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0304038 · Cited by 12

Distribution-free junta testing

Liu, Z., Chen, X., Servedio, R. A., Sheng, Y., & Xie, J. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188842 · Cited by 11

Testing Non-uniform k-Wise Independent Distributions over Product Spaces

Rubinfeld, R., & Xie, N. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14165-2_48 · Cited by 11

2-Transitivity is Insufficient for Local Testability

Grigorescu, E., Kaufman, T., & Sudan, M. (2012) · Computational Complexity · doi:10.1007/s00037-012-0055-3 · Cited by 11

Relaxed Locally Correctable Codes in Computationally Bounded Channels

Blocki, J., Gandikota, V., Grigorescu, E., & Zhou, S. (2019) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2019.8849322 · Cited by 11

Randomized Algorithms

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

Cube Attack on Stream Ciphers using a Modified Linearity Test

Srinivasan, C., Pillai, U. U., Lakshmy, K. V., & Sethumadhavan, M. (2015) · Journal of Discrete Mathematical Sciences and Cryptography · doi:10.1080/09720529.2014.995967 · Cited by 11

Local Decoding and Testing for Homomorphisms

Grigorescu, E., Kopparty, S., & Sudan, M. (2006) · Lecture notes in computer science · doi:10.1007/11830924_35 · Cited by 11

On Active and Passive Testing

Alon, N., Hod, R., & Weinstein, A. (2016) · Combinatorics Probability Computing · doi:10.1017/s0963548315000292 · Cited by 11

Probabilistic Proof Systems: A Primer

Goldreich, O. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981530 · Cited by 11

Short Locally Testable Codes and Proofs

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

The power of adaptiveness and additional queries in random-self-reductions

Joan Feigenbaum, A., Fortnow, L., Lund, C., & Spielman, D. A. (2003) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1992.215408 · Cited by 11

Quantum Testers for Hidden Group Properties

Friedl, K., Sántha, M., Magniez, F., & Sen, P. (2009) · Fundamenta Informaticae · doi:10.3233/fi-2009-0046 · Cited by 11

New sublinear methods in the struggle against classical problems

Rubinfelds, R., & Onak, K. (2010) · Cited by 11

Testing multivariate linear functions

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

Succinct Representation of Codes with Applications to Testing

Grigorescu, E., Kaufman, T., & Sudan, M. (2012) · SIAM Journal on Discrete Mathematics · doi:10.1137/100818364 · Cited by 10

Investigating Cube Attacks on the Authenticated Encryption Stream Cipher MORUS

Salam, I., Simpson, L. R., Bartlett, H., Dawson, E., Pieprzyk, J., & Wong, K. K. (2017) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom/bigdatase/icess.2017.337 · Cited by 10

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Kothari, P. K., & Manohar, P. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649640 · Cited by 10

Streaming Property Testing of Visibly Pushdown Languages

François, N., Magniez, F., de Rougemont, M., & Serre, O. (2016) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.esa.2016.43 · Cited by 10

AND testing and robust judgement aggregation

Filmus, Y., Lifshitz, N., Minzer, D., & Mossel, E. (2020) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3357713.3384254 · Cited by 10

3-bit dictator testing: 1 vs. 5/8

O’Donnell, R., & Wu, Y. (2009) · KiltHub Repository · doi:10.5555/1496770.1496811 · Cited by 10

Distribution-Free Connectivity Testing

Halevy, S., & Eyal Kushilevitz, Z. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27821-4_35 · Cited by 10

Distribution-Free Connectivity Testing for Sparse Graphs

Halevy, S., & Eyal Kushilevitz, Z. (2007) · Algorithmica · doi:10.1007/s00453-007-9054-1 · Cited by 10

A Query Efficient Non-adaptive Long Code Test with Perfect Completeness

Tamaki, S., & Yoshida, Y. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_55 · Cited by 10

Self-Testing without the Generator Bottleneck

Ergün, F., Kumar, S. R., & Sivakumar, D. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539796311168 · Cited by 10

A CASE STUDY IN ALGORITHM ENGINEERING FOR GEOMETRIC COMPUTING

Tamassia, R., & Vismara, L. (2001) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195901000390 · Cited by 10

Efficiently Testing Sparse GF(2) Polynomials

Diakonikolas, I., Lee, H. K., Matulef, K., Servedio, R. A., & Wan, A. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_41 · Cited by 10

Cryptanalysis of hardware-oriented ciphers the Knapsack generator, and SHA-1

Knellwolf, S. (2012) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-a-007554419 · Cited by 10

Quantum soundness of the classical low individual degree testPreprint

Ji, Z., Natarajan, A., Vidick, T., Wright, J., & Yuen, H. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.12982 · Cited by 10

The power of adaptiveness and additional queries in random-self-reductions

Joan Feigenbaum, A., Fortnow, L., Lund, C., & Spielman, D. A. (1994) · Computational Complexity · doi:10.1007/bf01202287 · Cited by 10

A characterization of locally testable affine-invariant properties via decomposition theorems

Yoshida, Y. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591802 · Cited by 9

A Brief Introduction to Property Testing

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

Direct Sum Testing

David, R., Dinur, I., Goldenberg, E., Kindler, G., & Shinkar, I. (2017) · SIAM Journal on Computing · doi:10.1137/16m1061655 · Cited by 9

Testing for Concise Representations

Diakonikolas, I., Lee, H. K., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R. A., & Wan, A. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.4389524 · Cited by 9

Estimating the Distance from Testable Affine-Invariant Properties

Hatami, H., & Lovett, S. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.33 · Cited by 9

On the query complexity of testing orientations for being Eulerian

Fischer, E., Lachish, O., Matsliah, A., Newman, I., & Yahalom, O. (2012) · ACM Transactions on Algorithms · doi:10.1145/2151171.2151178 · Cited by 9

On the Query Complexity of Testing Orientations for Being Eulerian

Fischer, E., Lachish, O., Newman, I., Matsliah, A., & Yahalom, O. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85363-3_32 · Cited by 9

Guest Column

Kopparty, S., & Saraf, S. (2016) · ACM SIGACT News · doi:10.1145/2993749.2993761 · Cited by 9

Space Complexity Vs. Query Complexity

Lachish, O., Newman, I., & Shapira, A. (2008) · Computational Complexity · doi:10.1007/s00037-008-0239-z · Cited by 9

Testing of matrix-poset properties

Fischer, E., & Newman, I. (2007) · COMBINATORICA · doi:10.1007/s00493-007-2154-3 · Cited by 9

Algebraic testing and weight distributions of codes

Kiwi, M. A. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(02)00816-2 · Cited by 9

Functions that have read-twice constant width branching programs are not necessarily testable

Fischer, E. O., & Newman, I. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2002.1004342 · Cited by 9

Sparse Polynomial Interpolation and Testing

Arnold, A. (2016) · UWSpace (University of Waterloo) · Cited by 9

Sample-based high-dimensional convexity testingPreprint

Chen, X., Freilich, A., Servedio, R. A., & Sun, T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1706.09362 · Cited by 9

Corrigendum to: The Cube Attack on Stream Cipher Trivium and Quadraticity Tests.

Mroczkowski, P., & Szmidt, J. (2011) · Cited by 9

Guest column

Bhattacharyya, A. (2013) · ACM SIGACT News · doi:10.1145/2556663.2556678 · Cited by 8

Testing Odd-Cycle-Freeness in Boolean Functions

Bhattacharyya, A., Grigorescu, E., Raghavendra, P., & SHAPIRA, A. (2012) · Combinatorics Probability Computing · doi:10.1017/s0963548312000363 · Cited by 8

Checking Approximate Computations of Polynomials and Functional Equations

Ergün, F., Kumar, S. R., & Rubinfeld, R. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539798337613 · Cited by 8

Approximate testing with error relative to input size

Kiwi, M. A., Magniez, F., & Sántha, M. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00004-7 · Cited by 8

Spectrum-Based Fault Localization in Regression Testing

Tiwari, S., Mishra, K. K., Kumar, A., & Misra, A. K. (2011) · International Conference on Information Technology: New Generations · doi:10.1109/itng.2011.40 · Cited by 8

Hardness of Approximation

Vazirani, V. V. (2003) · Springer eBooks · doi:10.1007/978-3-662-04565-7_29 · Cited by 8

Testing graph isomorphism

Fischer, E., & Matsliah, A. (2006) · Symposium on Discrete Algorithms · doi:10.5555/1109557.1109591 · Cited by 8

Conditional Inapproximability and Limited Independence

Austrin, P. (2008) · KTH Publication Database DiVA (KTH Royal Institute of Technology) · Cited by 8

Distribution-free Junta TestingPreprint

Chen, X., Liu, Z., Servedio, R. A., Sheng, Y., & Xie, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.04859 · Cited by 8

Hardness Self-Amplification: Simplified, Optimized, and Unified

Hirahara, S., & Shimizu, N. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585189 · Cited by 7

A New Model for Error-Tolerant Side-Channel Cube Attacks

Li, Z., Zhang, B., Fan, J., & Verbauwhede, I. M. R. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40349-1_26 · Cited by 7

c 3 -Locally Testable Codes from Lossless Expanders

Lin, T.-C., & Hsieh, M.-H. (2022) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit50566.2022.9834679 · Cited by 7

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

Guruswami, V., Lin, B., Ren, X., Sun, Y., & Wu, K. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649771 · Cited by 7

Robust characterizations of k‐wise independence over product spaces and related testing results

Rubinfeld, R., & Xie, N. (2012) · Random Structures and Algorithms · doi:10.1002/rsa.20423 · Cited by 7

Hardness of Solving Sparse Overdetermined Linear Systems

Guruswami, V., & Raghavendra, P. (2009) · ACM Transactions on Computation Theory · doi:10.1145/1595391.1595393 · Cited by 7

Testing properties of boolean functions

O’Donnell, R., & Blais, E. (2012) · Cited by 7

Algebraic Properties of the Cube Attack.

Quedenfeld, F.-M., & Wolf, C. (2013) · Cited by 7

Limitations of Local Filters of Lipschitz and Monotone Functions

Awasthi, P., Jha, M. K., Molinaro, M., & Raskhodnikova, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32512-0_32 · Cited by 7

Probabilistic abstraction for model checking: an approach based on property testing

Laplante, S., Lassaigne, R., Magniez, F., Sylvain Peyronnet, D., & de Rougemont, M. (2003) · ACM/IEEE Symposium on Logic in Computer Science (LICS) · doi:10.1109/lics.2002.1029815 · Cited by 7

Smooth and Strong PCPs

Paradise, O. (2021) · Computational Complexity · doi:10.1007/s00037-020-00199-3 · Cited by 7

Relaxed Locally Correctable Codes in Computationally Bounded Channels

Blocki, J., Gandikota, V., Grigorescu, E., & Zhou, S. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3076396 · Cited by 7

The Power and Limitations of Uniform Samples in Testing Properties of Figures

Berman, P., Murzabulatov, M., & Raskhodnikova, S. (2018) · Algorithmica · doi:10.1007/s00453-018-0467-9 · Cited by 7

The Role of Measurement in Software Safety Assessment

Fenton, N. (1997) · Springer eBooks · doi:10.1007/978-1-4471-0921-1_11 · Cited by 7

Testing Linear-Invariant Non-Linear Properties

Bhattacharyya, A., Chen, V., Sudan, M., & Xie, N. (2009) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2009.1823 · Cited by 7

On self-testing without the generator bottleneck

Ravikumar, S., & Sivakumar, D. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60692-0_53 · Cited by 7

Testing of exponentially large codes, by a new extension to Weil bound for character sums.Preprint

Kaufman, T., & Lovett, S. (2010) · Electronic colloquium on computational complexity · Cited by 7

Hierarchy Theorems for Property Testing

Goldreich, O., Krivelevich, M., Newman, I., & Rozenberg, E. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03685-9_38 · Cited by 7

Almost Optimal Testers for Concise RepresentationsPreprint

Bshouty, N. H. (2019) · arXiv (Cornell University) · doi:10.4230/lipics.approx/random.2020.5 · Cited by 7

New Results on Quantum Property TestingPreprint

Chakraborty, S., Fischer, E., Matsliah, A., & de Wolf, R. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1005.0523 · Cited by 7

Gowers Norm, Function Limits, and Parameter Estimation

Yoshida, Y. (2015) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974331.ch96 · Cited by 6

Local correction of juntas

Alon, N., & Weinstein, A. (2011) · Information Processing Letters · doi:10.1016/j.ipl.2011.12.005 · Cited by 6

Sparse Combinatorial Structures: Classification and Applications

Nešetřil, J., & de Mendez, P. O. (2011) · International Congress of Mathematicians (ICM) · doi:10.1142/9789814324359_0156 · Cited by 6

Exponentially improved algorithms and lower bounds for testing signed majorities

Ron, D., & Servedio, R. A. (2013) · Symposium on Discrete Algorithms · doi:10.5555/2627817.2627913 · Cited by 6

Multi-server verifiable delegation of computations: Unconditional security and practical efficiency

Zhang, L. F. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104740 · Cited by 6

Testing Convexity Properties of Tree Colorings

Fischer, E., & Yahalom, O. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-70918-3_10 · Cited by 6

Cube Cryptanalysis of LBlock with Noisy Leakage

Li, Z., Zhang, B., Yao, Y., & Lin, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-37682-5_11 · Cited by 6

Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries

Dolev, E., & Ron, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15369-3_40 · Cited by 6

Tight Lower Bounds for Testing Linear Isomorphism

Grigorescu, E., Wimmer, K., & Xie, N. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-40328-6_39 · Cited by 6

Time-Resolved VUV Excited Luminescence of $\hbox {Y}_{2}\hbox {O}_{3}\hbox {--} \hbox {Yb}$ Nanoparticles

Amans, D., Belsky, A. N., Dujardin, C., Hovsepyan, A., Kamenskikh, I. A., Kotlov, A., Ledoux, G., Fedorov, N., Pedrini, C., & Васильев, А. Н. (2010) · IEEE Transactions on Nuclear Science · doi:10.1109/tns.2009.2035696 · Cited by 6

Testing commutativity of a group and the power of randomization

Pak, I. (2012) · LMS Journal of Computation and Mathematics · doi:10.1112/s1461157012000046 · Cited by 6

Optimal Testing of Reed-Muller Codes

Bhattacharyya, A., Kopparty, S., Schoenebeck, G. R., Sudan, M., & Zuckerman, D. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_19 · Cited by 6

Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown

Ron, D., & Tsur, G. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13073-1_13 · Cited by 6

Approximate Judgement Aggregation

Nehama, I. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25510-6_26 · Cited by 6

Guest column: testing linear properties

Sudan, M. (2011) · ACM SIGACT News · doi:10.1145/1959045.1959062 · Cited by 6

Proximity Oblivious Testing and the Role of Invariances

Goldreich, O., & Kaufman, T. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22670-0_19 · Cited by 6

Additive Combinatorics and Theoretical Computer Science

Trevisan, L. (2009) · Cited by 6

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