The DOI matches its Crossref record; 21 of the 30 references it cites were found in a registry or an index.
Self-testing/correcting with applications to numerical problems
Open accessOverview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“If the BLR test is run n times, then we can conclude that PC(K,V) is linear with probability 1-2⁻ⁿ.”
From Cube attacks on round-reduced TinyJAMBU (2022) · cites this paper as [19]
Citations
Cites
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
Self-citationSchnelle 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
Self-citationLipton, R. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/13 · Cited by 270
Research works printed but not linked: 2
- Beigel, 1990, On the Complexity of Coherent Sets, AT & T Technical Memorandum
- Cleve, 1990, A Note on Self-Testing/Correcting Methods for Trigonometric Functions, ICSI Technical Report TR-90-032
Cited by
Sorted by citations
Items 601–696 of 696
Alternative Notions of Approximation and Space-Bounded Computations
Beygelzimer, A. (2003)
Application of Ɛ-testers algorithms under sketch and streaming calculation model in robot navigation
Lucatero, C. R. (2009) · WSEAS Transactions on Computers archive
Error detection in number-theoretic and algebraic algorithms
Vasiga, T. (2008) · UWSpace (University of Waterloo)
Indistinguishability and First-Order Logic
Jordan, S., & Zeugmann, T. (2008) · Springer eBooks · doi:10.1007/978-3-540-79228-4_8
An Experimental Study to Compare the Use of Metamorphic Testing and Assertion
Zhang, Chan, Z. E., Tse, W., Hu, T., Zhang, Z., Chan, W. K., & Hu, P. (2009)
Studies in the efficiency and (versus) security of cryptographic tasks
Barak, B., & Mahmoody, M. (2010)
Dilation, Transport, Visibility and Fault-Tolerant Algorithms
Mathematisch-naturwissenschaftlichen Fakultät, I., & Bonn, R. F.-W.-U. (2014)
Space Complexity vs. Query Complexity
Lachish, O., Newman, I., & Shapira, A. (2006) · Lecture notes in computer science · doi:10.1007/11830924_39
Checking properties of polynomials
Codenotti, B., Ergün, F., Gemmell, P. S., & Kumar, S. R. (1997) · Lecture notes in computer science · doi:10.1007/3-540-63165-8_178
Improved Streaming Algorithm for Dyck(s) Recognition
Jain, A. (2014) · Research Archive of Indian Institute of Technology Hyderabad (Indian Institute of Technology Hyderabad)
Characterizations of Locally Testable Linear- and Affine-Invariant Families
Li, A., & Pan, Y. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22685-4_41
A combinatorial characterization of smooth LTCs and applications
Ben‐Sasson, E., & Viderman, M. (2016) · Random Structures and Algorithms · doi:10.1002/rsa.20637
Utilizing Probabilistic Linear Equations in Cube Attacks
Yao, Y., Zhang, B., & Wu, W. (2016) · Journal of Computer Science and Technology · doi:10.1007/s11390-016-1629-3
Local list decoding of homomorphisms
Grigorescu, E. (2006) · DSpace@MIT (Massachusetts Institute of Technology)
Schwenk, J., & Beutelspacher, A. (1997) · Vieweg+Teubner eBooks · doi:10.1007/978-3-663-12412-2_4
Needles in a Haystack: the Class NP
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0004
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0006
Counting, Sampling, and Statistical Physics
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0013 · Cited by 1
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0003
(2006) · I.B.Tauris eBooks · doi:10.5040/9780755625963.0007
The Grand Unified Theory of Computation
Cristopher, M. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0007
Interaction and Pseudorandomness
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0011
Who is the Hardest One of All? NP-Completeness
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0005
When Formulas Freeze: Phase Transitions in Computation
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0014
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0008
The Kahr-Moore-Wang Class Contains Untestable Properties
Jordan, C., & Zeugmann, T. (2016) · Baltic Journal of Modern Computing · doi:10.22364/bjmc.2016.4.4.11
Secure Modular Exponentiation Outsource With Two Untrusted Programs and Improved Checkability.
Ma, Y., Tian, H., & Wei, B. (2016) · Journal of information science and engineering
Self-Testing of One-Qubit GatesPreprint
van Dam, W., Magniez, F., Mosca, M., & Sántha, M. (1999) · arXiv (Cornell University)
Notes for the first lecture in a course on Property Testing
Goldreich, O. (2016)
Classical and quantum algorithms for algebraic problems
Ivanyos, G. (2007)
Time-Space Tradeoffs and Query Complexity in Statistics, Coding Theory, and Quantum Computing
Machmouchi, W. (2013) · ResearchWorks at the University of Washington (University of Washington)
Wootters, M. K. (2014) · Deep Blue (University of Michigan)
On the nature of the Theory of Computation (ToC).Preprint
Wigderson, A. (2018) · Electronic colloquium on computational complexity
Analysis of Authenticated Encryption Based on Stream Ciphers
Salam, I. (2018) · Queensland University of Technology · doi:10.5204/thesis.eprints.117673
Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity
Grigorescu, E., Kumar, A. S., & Wimmer, K. (2019) · SIAM Journal on Discrete Mathematics · doi:10.1137/18m1217978
Explicit Strong LTCs with inverse poly-log rate and constant soundness.Preprint
Viderman, M. (2015) · Electronic colloquium on computational complexity
Property Testing and Expansion in Cubical Complexes
Garber, D., & Vishne, U. (2019) · Discrete & Computational Geometry · doi:10.1007/s00454-019-00160-4
Approximations in Model-Checking and Testing
Gaudel, M.-C., Lassaigne, R., Magniez, F., & de Rougemont, M. (2013)
Kiyoshima, S. (2023) · Journal of Cryptology · doi:10.1007/s00145-023-09448-4
Efficiently Testing Sparse GF(2) PolynomialsPreprint
Diakonikolas, I., Lee, H. K., Matulef, K., Servedio, R. A., & Wan, A. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0805.1765
Lower bounds for adaptive linearity testsPreprint
Lovett, S. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0802.2857
Hyperfiniteness of Real-World Networks
Honda, Y., Inoue, Y., Ito, H., Sasajima, M., Teruyama, J., & Uno, Y. (2019) · The Review of Socionetwork Strategies · doi:10.1007/s12626-019-00051-3
Cube distinguisher extraction using division property in block ciphers
Eskandari, Z., & Bafghi, A. G. (2019) · IET Information Security · doi:10.1049/iet-ifs.2018.5252
Testing membership for timed automata
Lassaigne, R., & de Rougemont, M. (2023) · Acta Informatica · doi:10.1007/s00236-023-00442-8
An Optimal Tester for k-Linear
Bshouty, N. H. (2022) · Lecture notes in computer science · doi:10.1007/978-3-030-96731-4_17
On Tolerant Testing and Tolerant Junta Testing
Levi, A. (2020) · UWSpace (University of Waterloo)
A Non-Extendibility Certificate for Submodularity and Applications
Bhaskar, U., & Kumar, G. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-58150-3_49
PCP Theorems, SETH and More: Towards Proving Sub-linear Time InapproximabilityPreprint
Ma, H., & Li, J. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2011.02320
GSF-locality is not sufficient for proximity-oblivious testing
Adler, I., Köhler, N., & Peng, P. (2021) · White Rose Research Online (University of Leeds, The University of Sheffield, University of York) · doi:10.48550/arxiv.2105.08490
The PCP-like Theorem for Sub-linear Time InapproximabilityPreprint
Ma, H., & Li, J. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2107.01520
Grover’s Algorithm and Walsh Spectrum
Sapv, T., Bera, D., Maitra, A., & Maitra, S. (2021) · SpringerBriefs in computer science · doi:10.1007/978-981-16-3061-3_3
Sublinear-Time Computation in the Presence of Online ErasuresPreprint
Kalemaj, I., Raskhodnikova, S., & Varma, N. M. (2021) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2022.90
Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas
Babai, L. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20712-9_13
Fault Detection Tests for Stuck-at Faults on Parity Counter Inputs
Романов, Д. С. (2015) · Computational Mathematics and Modeling · doi:10.1007/s10598-015-9282-1
De, A., Nadimpalli, S., & Servedio, R. A. (2022) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977073.94
Du, D., & Ko, K.-I. (2000) · doi:10.1002/9781118032916.biblio
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0001
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0015
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0002
Harsha, P. (2016) · Encyclopedia of Algorithms · doi:10.1007/978-1-4939-2864-4_707
陈, 豪. (2009) · Science in China Series A-Mathematics (in Chinese) · doi:10.1360/za2009-39-10-1234
Cahill, K. M. (2020) · Fordham University Press eBooks · doi:10.1515/9780823295708-025
Minzer, D. (2022) · ACM eBooks · doi:10.1145/3568031.3568035
Minzer, D. (2022) · ACM eBooks · doi:10.1145/3568031.3568038
Minzer, D. (2022) · doi:10.1145/3568031.3568033
Monotonicity Testing and Directed Isoperimetric Inequalities
Minzer, D. (2022) · ACM eBooks · doi:10.1145/3568031.3568034
Minzer, D. (2022) · doi:10.1145/3568031.3568040
Minzer, D. (2022) · doi:10.1145/3568031.3568039
Minzer, D. (2022) · doi:10.1145/3568031.3568032
The Biased Long Code and Hardness of Vertex Cover
Minzer, D. (2022) · ACM eBooks · doi:10.1145/3568031.3568037
Almost Optimal Proper Learning and Testing Polynomials
Bshouty, N. H. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-20624-5_19
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0007
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0004
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0003
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.005.0001
(2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.002.0006
On One-Sided Testing Affine Subspaces
Bshouty, N. H. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30448-4_12
Cube Attacks on Round-Reduced Grain-128AEAD
Teng, W. L., Salam, I., Yau, W., & Yew, T. J. (2023) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-031-50215-6_8
Almost Optimal Adaptive Proper Learning PolynomialsPreprint
Bshouty, N. H. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4805894
Two-Sided Convexity Testing with Certificates
Dumitrescu, A. (2024) · Studia Scientiarum Mathematicarum Hungarica · doi:10.1556/012.2024.04308
A Dense Model Theorem for the Boolean Slice
Kalai, G., Lifshitz, N., Minzer, D., & Ziegler, T. (2024) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs61266.2024.00056
Goldreich, O., & Tauber, L. (2025) · Lecture notes in computer science · doi:10.1007/978-3-031-88946-2_23
SIGACT News Complexity Theory Column 126 Locally Decodable Codes for Insertions and Deletions
Grigorescu, E. (2025) · ACM SIGACT News · doi:10.1145/3767145.3767151
Bounds for the average degree-k monomial density of Boolean functions
Sălăgean, A., & Reyes-Paredes, P. (2025) · Cryptography and Communications · doi:10.1007/s12095-025-00839-x
Property Testing with Online Adversaries
Ben‐Eliezer, O., Kelman, E., Meir, U., & Raskhodnikova, S. (2025) · ACM Transactions on Computation Theory · doi:10.1145/3778165
Application of ε -testers algorithms under sketch calculation model in robot navigation problem
Lucatero, C. R. (2009) · International Conference on Systems
Optimal Random Self-Reductions for All Linear Problems
Hirahara, S., & Shimizu, N. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800773
Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
Grigorescu, E., Kumar, V. M., Manohar, P., & Mon, G. (2026) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3798129.3800850
Randomized Self-Reduction for Fault-Resilient MAYO Signatures
Chatterjee, D., & Dankbaar, V. (2026) · doi:10.1145/3847162.3849235
Almost optimal adaptive proper learning polynomials
Bshouty, N. H. (2026) · Theoretical Computer Science · doi:10.1016/j.tcs.2026.116280
Extremal Problems for Sparse Graphs
Nešetřil, J., & de Mendez, P. O. (2010) · Bolyai Society mathematical studies · doi:10.1007/978-3-642-14444-8_13
Teste de propriedades em torneios
Stagni, H. (2015) · doi:10.11606/d.45.2015.tde-21072015-112930
Aplicaciones no elementales de un teorema elemental
Montoya, J. A. (2014) · Gaceta de la Real Sociedad Matematica Española
Metadata
- Authors
- Blum, M., Luby, M., & Rubinfeld, R.
- Affiliations
- University of California, Berkeley (US)
- International Computer Science Institute (US)
- Cornell University (US)
- Venue
- Journal of Computer and System Sciences
- Publisher
- Elsevier BV
- Published
- 1993-12
- Volume
- 47
- Issue
- 3
- Pages
- 549-595
- ISSN
- 0022-0000 (ISSN-L)
- OpenAlex
- W3004537778
- Cited by
- 712
- References
- 30
- Citations by year
- 2026: 4 · 2025: 12 · 2024: 8 · 2023: 8 · 2022: 23 · 2021: 19 · 2020: 26 · 2019: 17 · 2018: 24 · 2017: 21 · 2016: 31 · 2015: 27 · 2014: 25 · 2013: 35 · 2012: 33
- FWCI
- 6.50
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- Locations
- Journal of Computer and System Sciences (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Software › Software Testing and Debugging Techniques
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Keywords
- fault-tolerant computation, numerical algorithms, integer multiplication, modular multiplication, matrix multiplication, matrix inversion, matrix determinants, matrix rank, integer division, modular exponentiation, polynomial multiplication, program correctness
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
