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
Freivalds, R. (1979) · Lecture notes in computer science · doi:10.1007/3-540-09526-8_5 · Cited by 232
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
Self-citationProceedings of the 42nd ACM symposium on Theory of computing
Mitzenmacher, M., & Schulman, L. J. (2010) · Cited by 167
A mathematical theory of self-checking, self-testing and self-correcting programs
Rubinfeld, R. (1991) · Cited by 53
Self-citationSelf-testing polynomial functions efficiently and over rational domains
Rubinfeld, R., & Sudan, M. (1992) · Cited by 42
Self-citationProgram result checking against adaptive programs and in cryptographic settings
Blum, M., Luby, M. G., & Rubinfeld, R. (1991) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/002/06 · Cited by 36
Self-citationEfficient generation of random nonsingular matrices
Randall, D. (1993) · Random Structures and Algorithms · doi:10.1002/rsa.3240040108 · Cited by 29
Efficient Checkers for Number-Theoretic Computations
Adleman, L. M., Huang, M. D., & Kompella, K. (1995) · Information and Computation · doi:10.1006/inco.1995.1125 · Cited by 21
Designing Checkers for Programs that Run in Parallel
Rubinfeld, R. (1996) · Algorithmica · doi:10.1007/bf01961540 · Cited by 16
Self-citationProgram Correctness: Can One Test For It?
Blum, M., & Raghavan, P. (1989) · IFIP Congress · Cited by 11
Self-citationA note on probabilistically verifying integer and polynomial products
Kaminski, M. (1989) · Journal of the ACM · doi:10.1145/58562.214082 · Cited by 10
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
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,449
Property testing and its connection to learning and approximation
Goldreich, O., Goldwasser, S., & Ron, D. (1998) · Journal of the ACM · doi:10.1145/285055.285060 · Cited by 1,019
Robust Characterizations of Polynomials with Applications to Program Testing
Rubinfeld, R., & Sudan, M. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539793255151 · Cited by 794
Self-citationA Survey on Metamorphic Testing
Segura, S., Fraser, G., Sánchez, A. B., & Ruiz–Cortés, A. (2016) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2016.2532875 · Cited by 571
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
