The DOI matches its Crossref record; 22 of the 22 references it cites were found in a registry or an index.
Designing programs that check their work
Abstract
A program correctness checker is an algorithm for checking the output of a computation. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class P of problems solvable in polynomial time. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Finally it characterizes the problems that can be checked.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 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
New hash functions and their use in authentication and set equality
Wegman, M. N., & Carter, J. L. (1981) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(81)90033-7 · Cited by 1,402
Efficient randomized pattern-matching algorithms
Karp, R. M., & Rabin, M. O. (1987) · IBM Journal of Research and Development · doi:10.1147/rd.312.0249 · Cited by 1,269
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Parallel Algorithms for Shared-Memory Machines
Karp, R. M., & Ramachandran, V. (1990) · Elsevier eBooks · doi:10.1016/b978-0-444-88071-0.50022-9 · Cited by 687
A taxonomy of problems with fast parallel algorithms
Cook, S. A. (1985) · Information and Control · doi:10.1016/s0019-9958(85)80041-3 · Cited by 641
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
Babai, L., & Moran, S. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90028-1 · Cited by 589
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
Goldreich, O., Micali, S., & Wigderson, A. (1986) · 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) · doi:10.1109/sfcs.1986.47 · Cited by 549
Social processes and proofs of theorems and programs
De Millo, R. A., Lipton, R. J., & Perlis, A. J. (1979) · Communications of the ACM · doi:10.1145/359104.359106 · Cited by 537
Private coins versus public coins in interactive proof systems
Goldwasser, S., & Sipser, M. (1986) · Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86 · doi:10.1145/12130.12137 · Cited by 399
Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds
Pólya, G., & Read, R. C. (1987) · Springer eBooks · doi:10.1007/978-1-4612-4664-0 · Cited by 390
Self-testing/correcting with applications to numerical problems
Blum, M., Luby, M., & Rubinfeld, R. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100225 · Cited by 303
Self-citationTwo notions of correctness and their relation to testing
Budd, T. A., & Angluin, D. (1982) · Acta Informatica · doi:10.1007/bf00625279 · Cited by 260
Lipton, R. (1991) · DIMACS Series in Discrete Mathematics and Theoretical Computer Science · doi:10.1090/dimacs/002/13 · Cited by 255
Hiding 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
Random self-reducibility and zero knowledge interactive proofs of possession of information
Tompa, M., & Woll, H. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.49 · Cited by 224
A note on the graph isomorphism counting problem
Mathon, R. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90004-8 · Cited by 200
Group-Theoretic Algorithms and Graph Isomorphism
(1982) · Lecture Notes in Computer Science · doi:10.1007/3-540-11493-9 · Cited by 196
Exact and approximate membership testers
Carter, L., Floyd, R. W., Gill, J. T., III, Markowsky, G., & Wegman, M. N. (1978) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800133.804332 · Cited by 138
On helping by robust oracle machines
Ko, K. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90078-8 · Cited by 64
Program Correctness: Can One Test For It?
Blum, M., & Raghavan, P. (1989) · IFIP Congress · Cited by 11
Self-citation
Cited by
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
Software protection and simulation on oblivious RAMs
Goldreich, O., & Ostrovsky, R. (1996) · Journal of the ACM · doi:10.1145/233551.233553 · Cited by 1,617
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,413
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
Metadata
- Authors
- Blum, M., & Kanna, S.
- Venue
- Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89
- Publisher
- ACM Press
- Published
- 1989
- Pages
- 86-97
- OpenAlex
- W2002032317
- Cited by
- 287
- References
- 22
- FWCI
- 5.53
- Type
- conference paper
- Language
- en
- Open access
- closed
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.