The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Designing programs that check their work
Open accessAbstract
A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that instance is correct. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class FP of functions computable in polynomial time. Problems in FP for which checkers are presented in this paper include Sorting, Matrix Rank and GCD. 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. Two structural theorems are proven here. One is a characterization of problems that can be checked. The other theorem establishes equivalence classes of problems such that whenever one problem in a class is checkable, all problems in the class are checkable.
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
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
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
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
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
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
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
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
The correctness problem in computer science
(1983) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(83)90038-1 · Cited by 354
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-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-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
Checking the correctness of memories
Blum, M., Evans, W., Gemmell, P., Kannan, S., & Naor, M. (1994) · Algorithmica · doi:10.1007/bf01185212 · Cited by 201
Self-citationA note on the graph isomorphism counting problem
Mathon, R. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90004-8 · Cited by 200
Random-Self-Reducibility of Complete Sets
Feigenbaum, J., & Fortnow, L. (1993) · SIAM Journal on Computing · doi:10.1137/0222061 · Cited by 162
On helping by robust oracle machines
Ko, K. (1987) · Theoretical Computer Science · doi:10.1016/0304-3975(87)90078-8 · Cited by 64
On the random-self-reducibility of complete sets
Feigenbaum, J., & Fortnow, L. (2002) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1991.160252 · Cited by 45
Locally random reductions in interactive complexity theory
Feigenbaum, J. (1993) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/013/05 · 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
Program Correctness: Can One Test For It?
Blum, M., & Raghavan, P. (1989) · IFIP Congress · Cited by 11
Self-citation
Cited by
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
Watermarking, tamper-proofing, and obfuscation - tools for software protection
Collberg, C. S., & Thomborson, C. (2002) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2002.1027797 · Cited by 735
A secure and reliable bootstrap architecture
Arbaugh, W. A., Farber, D. J., & Smith, J. M. (2002) · Proceedings. 1997 IEEE Symposium on Security and Privacy (Cat. No.97CB36097) · doi:10.1109/secpri.1997.601317 · Cited by 562
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
Kabanets, V., & Impagliazzo, R. (2004) · computational complexity · doi:10.1007/s00037-004-0182-6 · Cited by 378
Metadata
- Authors
- Blum, M., & Kannan, S.
- Venue
- Journal of the ACM
- Published
- 1995-01-03
- Volume
- 42
- Issue
- 1
- Pages
- 269-291
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W1996839061
- Cited by
- 393
- References
- 30
- FWCI
- 13.77
- Type
- journal article
- 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.