The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Self-testing/correcting with applications to numerical problems
Open accessAbstract
Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f.Should we trust that P works correctly?A self-testing/correcting pair allows us to: (1) estimate the probability that P(x) 5~ f(x) when x is randomly chosen; (2) on any input x, compute f(x) correctly as long as P is not too faulty on average.Furthermore, both (1) and ( 2) take time only slightly more than the original running time of P.We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical problems, including integer multiplication, modular multiplication, matrix multiplication, inverting matrices, computing the determinant of a matrix, computing the rank of a matrix, integer division, modular exponentiation and polynomial multiplication.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
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,546
How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
Blum, M., & Micali, S. (1984) · SIAM Journal on Computing · doi:10.1137/0213053 · Cited by 1,322
Self-citationTrading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28396 · Cited by 632
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62223 · Cited by 468
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-citationDesigning programs that check their work
Blum, M., & Kanna, S. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73015 · Cited by 287
Self-citationLipton, R. (1991) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/002/13 · Cited by 255
How to generate cryptographically strong sequences of pseudo random bits
Blum, M., & Micali, S. (1982) · 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) · doi:10.1109/sfcs.1982.72 · Cited by 252
Self-citationHiding instances in multioracle queries
Beaver, D., & Feigenbaum, J. (1990) · Lecture Notes in Computer Science · doi:10.1007/3-540-52282-4_30 · Cited by 235
Freivalds, R. (1979) · Lecture notes in computer science · doi:10.1007/3-540-09526-8_5 · Cited by 232
Nondeterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (2002) · Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89520 · Cited by 188
Self-testing/correcting for polynomials and for approximate functions
Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., & Wigderson, A. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103429 · Cited by 181
Self-citationA mathematical theory of self-checking, self-testing and self-correcting programs
Rubinfeld, R. (1991) · Cited by 53
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
Program 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
Cited by
The LEDA platform for combinatorial and geometric computing
Mehlhorn, K., Näher, S., & Uhrig, C. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-63165-8_161 · Cited by 1,199
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
QuickCheck: a lightweight tool for random testing of Haskell programs
Claessen, K., & Hughes, J. (2011) · ACM SIGPLAN Notices · doi:10.1145/1988042.1988046 · Cited by 1,011
O'Donnell, R. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139814782 · Cited by 932
Raz, R., & Safra, S. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258641 · Cited by 834
Metadata
- Authors
- Blum, M., Luby, M., & Rubinfeld, R.
- Venue
- Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90
- Publisher
- ACM Press
- Published
- 1990
- Pages
- 73-83
- OpenAlex
- W2033361557
- Cited by
- 303
- References
- 22
- FWCI
- 8.31
- Type
- conference paper
- Language
- en
- Open access
- bronze
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.