{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T04:33:10Z","timestamp":1780633990948,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1994,9]]},"DOI":"10.1007\/bf01185212","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:46:54Z","timestamp":1108730814000},"page":"225-244","source":"Crossref","is-referenced-by-count":123,"title":["Checking the correctness of memories"],"prefix":"10.1007","volume":"12","author":[{"given":"M.","family":"Blum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"W.","family":"Evans","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"P.","family":"Gemmell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"M.","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF01185212_CR1","unstructured":"L. Adelman, M. Huang, and K. Kompella, Efficient checkers for number-theoretic computation, preprint."},{"key":"BF01185212_CR2","doi-asserted-by":"crossref","unstructured":"M. Blum, W. Evans, P Gemmell, S. Kannan, and M. Naor, Checking the correctness of memories,Proc. 32nd IEEE Symposium on Foundations of Computer Science, pages 90\u201399, 1991.","DOI":"10.1109\/SFCS.1991.185352"},{"key":"BF01185212_CR3","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Kannan, Designing programs that check their work,Proc. 21st ACM Symposium on Theory of Computing, pages 86\u201397, 1989.","DOI":"10.1145\/73007.73015"},{"key":"BF01185212_CR4","doi-asserted-by":"crossref","unstructured":"M. Blum, M. Luby, and R. Rubinfeld, Self-testing and self-correcting programs with applications to numerical problems,Proc. 22nd ACM Symposium on Theory of Computing, pages 73\u201383, 1990.","DOI":"10.1145\/100216.100225"},{"key":"BF01185212_CR5","first-page":"107","volume":"2","author":"M. Blum","year":"1991","unstructured":"M. Blum, M. Luby, and R. Rubinfeld,Program Result Checking Against Adaptive Programs and in Cryptographic Settings, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 2, pages 107\u2013118, 1991.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"issue":"2","key":"BF01185212_CR6","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1145\/103516.128681","volume":"38","author":"A. Condon","year":"1991","unstructured":"A. Condon, Space bounded probabilistic game automata,Journal of the ACM, 38(2):472\u2013494, April 1991.","journal-title":"Journal of the ACM"},{"issue":"4","key":"BF01185212_CR7","doi-asserted-by":"crossref","first-page":"800","DOI":"10.1145\/146585.146599","volume":"39","author":"C. Dwork","year":"1992","unstructured":"C. Dwork and L. Stockmeyer, Finite states verifiers, I: the power of interaction,Journal of the ACM, 39(4):800\u2013828, 1992.","journal-title":"Journal of the ACM"},{"key":"BF01185212_CR8","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel, and M. Sipser, On the power of multi-prover interactive protocols,Proc. 3rd IEEE Structure in Complexity Theory, pages 156\u2013161, 1988.","DOI":"10.1109\/SCT.1988.5275"},{"key":"BF01185212_CR9","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Towards a theory of software protection and simulation by oblivious RAMS,Proc. 19th ACM Symposium on Theory of Computing, pages 182\u2013194, 1987.","DOI":"10.1145\/28395.28416"},{"issue":"4","key":"BF01185212_CR10","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","volume":"33","author":"O. Goldreich","year":"1986","unstructured":"O. Goldreich, S. Goldwasser, and S. Micali, How to construct random functions,Journal of the ACM, 33(4):792\u2013807, October 1986.","journal-title":"Journal of the ACM"},{"key":"BF01185212_CR11","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Pseudo-random generators under uniform assumptions,Proc. 22nd ACM Symposium on Theory of Computing, pages 395\u2013405, 1990.","DOI":"10.1145\/100216.100270"},{"key":"BF01185212_CR12","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. A. Levin, and M. Luby Pseudo-random generators from one-way functions,Proc. 21st ACM Symposium on Theory of Computing, pages 12\u201324, 1989.","DOI":"10.1145\/73007.73009"},{"key":"BF01185212_CR13","doi-asserted-by":"crossref","unstructured":"R. Lipton, Efficient checking of computations,Proc. 7th Annual Symposium on Theoretical Aspects of Computer Science, pages 207\u2013215, 1990.","DOI":"10.1007\/3-540-52282-4_44"},{"key":"BF01185212_CR14","first-page":"191","volume":"2","author":"R. Lipton","year":"1991","unstructured":"R. Lipton,New Directions in Testing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 2, pages 191\u2013202, 1991.","journal-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science"},{"key":"BF01185212_CR15","first-page":"218","volume-title":"Lecture Notes in Computer Science, Vol. 435","author":"R. Merkle","year":"1990","unstructured":"R. Merkle. A certified digital signature, Manuscript, 1979. See alsoAdvances in Cryptology, Crypto '89 Proceedings, pages 218\u2013238, 1990. Lecture Notes in Computer Science, Vol. 435, Springer-Verlag, Berlin."},{"key":"BF01185212_CR16","doi-asserted-by":"crossref","unstructured":"J. Naor and M. Naor, Small-bias probability spaces: efficient constructions and applications,Proc. 22nd ACM Symposium on Theory of Computing, pages 213\u2013223, 1990.","DOI":"10.1145\/100216.100244"},{"key":"BF01185212_CR17","doi-asserted-by":"crossref","unstructured":"M. Naor and M. Yung, Universal one-way hash functions and their cryptographic applications,Proc. 21st ACM Symposium on Theory of Computing, pages 33\u201343, 1989.","DOI":"10.1145\/73007.73011"},{"key":"BF01185212_CR18","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, Efficient computation on oblivious RAMS,Proc. 22nd ACM Symposium on Theory of Computing, pages 514\u2013523, 1990.","DOI":"10.1145\/100216.100289"},{"issue":"2","key":"BF01185212_CR19","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"N. Pippenger and M. J. Fischer, Relations among complexity measures,Journal of the ACM, 26(2):361\u2013381, 1979.","journal-title":"Journal of the ACM"},{"key":"BF01185212_CR20","doi-asserted-by":"crossref","unstructured":"J. Rompel, One way functions are necessary and sufficient for secure signatures,Proc. 22nd ACM Symposium on Theory of Computing, pages 387\u2013394, 1990.","DOI":"10.1145\/100216.100269"},{"key":"BF01185212_CR21","doi-asserted-by":"crossref","unstructured":"A. Yao, Coherent functions and program checkers,Proc. 22nd ACM Symposium on Theory of Computing, pages 84\u201394, 1990.","DOI":"10.1145\/100216.100226"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185212.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01185212\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T21:00:43Z","timestamp":1586120443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01185212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":21,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF01185212"],"URL":"https:\/\/doi.org\/10.1007\/bf01185212","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}