{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T11:44:55Z","timestamp":1777376695948,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":83,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T00:00:00Z","timestamp":1357689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,1,9]]},"DOI":"10.1145\/2422436.2422481","type":"proceedings-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T12:58:22Z","timestamp":1357217902000},"page":"401-414","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Fast reductions from RAMs to delegatable succinct constraint satisfaction problems"],"prefix":"10.1145","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion and MIT, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Genkin","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eran","family":"Tromer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1760749.1760759"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803393"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880936"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/070709244"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_3_2_1_7_1","volume-title":"Fast reductions from RAMs to delegatable succinct constraint satisfaction problems","author":"Ben-Sasson E.","year":"2012","unstructured":"E. Ben-Sasson , A. Chiesa , D. Genkin , and E. Tromer . Fast reductions from RAMs to delegatable succinct constraint satisfaction problems , 2012 . Cryptology ePrint Archive, Report 2012\/071. E. Ben-Sasson, A. Chiesa, D. Genkin, and E. Tromer. Fast reductions from RAMs to delegatable succinct constraint satisfaction problems, 2012. Cryptology ePrint Archive, Report 2012\/071."},{"key":"e_1_3_2_1_8_1","volume-title":"On the concrete-efficiency threshold of probabilistically-checkable proofs","author":"Ben-Sasson E.","year":"2012","unstructured":"E. Ben-Sasson , A. Chiesa , D. Genkin , and E. Tromer . On the concrete-efficiency threshold of probabilistically-checkable proofs , 2012 . Electronic Colloquium on Computational Complexity, TR 12-045. E. Ben-Sasson, A. Chiesa, D. Genkin, and E. Tromer. On the concrete-efficiency threshold of probabilistically-checkable proofs, 2012. Electronic Colloquium on Computational Complexity, TR12-045."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007361"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.27"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_13_1","volume-title":"Mathematical theory of connecting networks and telephone traffic","author":"V. E.","year":"1965","unstructured":"V. E. Bene\\vs. Mathematical theory of connecting networks and telephone traffic . New York , Academic Press , 1965 . V. E. Bene\\vs. Mathematical theory of connecting networks and telephone traffic. New York, Academic Press, 1965."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_16"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185352"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(87)90232-8"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090262"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90005-0"},{"key":"e_1_3_2_1_22_1","first-page":"310","volume-title":"Proceedings of the 1st Symposium on Innovations in Computer Science, ICS '10","author":"Chiesa A.","year":"2010","unstructured":"A. Chiesa and E. Tromer . Proof-carrying data and hearsay arguments from signature cards . In Proceedings of the 1st Symposium on Innovations in Computer Science, ICS '10 , pages 310 -- 331 , 2010 . A. Chiesa and E. Tromer. Proof-carrying data and hearsay arguments from signature cards. In Proceedings of the 1st Symposium on Innovations in Computer Science, ICS '10, pages 310--331, 2010."},{"key":"e_1_3_2_1_23_1","volume-title":"Proof-carrying data: Secure computation on untrusted platforms (high-level description). The Next Wave: The National Security Agency's review of emerging technologies, 19(2):40--46","author":"Chiesa A.","year":"2012","unstructured":"A. Chiesa and E. Tromer . Proof-carrying data: Secure computation on untrusted platforms (high-level description). The Next Wave: The National Security Agency's review of emerging technologies, 19(2):40--46 , 2012 . A. Chiesa and E. Tromer. Proof-carrying data: Secure computation on untrusted platforms (high-level description). The Next Wave: The National Security Agency's review of emerging technologies, 19(2):40--46, 2012."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2033036.2033048"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881446"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804898"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090245"},{"key":"e_1_3_2_1_28_1","volume-title":"ECCC, 2010","author":"Cormode G.","year":"2010","unstructured":"G. Cormode , J. Thaler , and K. Yi . Verifying computations with streaming interactive proofs . ECCC, 2010 . Available at http:\/\/eccc.hpi-web.de\/report\/ 2010 \/159\/. G. Cormode, J. Thaler, and K. Yi. Verifying computations with streaming interactive proofs. ECCC, 2010. Available at http:\/\/eccc.hpi-web.de\/report\/2010\/159\/."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69407-6_21"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808763"},{"key":"e_1_3_2_1_32_1","first-page":"843","volume-title":"InciteReif93","author":"Fich F. E.","year":"1993","unstructured":"F. E. Fich . The complexity of computation on the parallel random access machine . InciteReif93 , pages 843 -- 899 , 1993 . F. E. Fich. The complexity of computation on the parallel random access machine. InciteReif93, pages 843--899, 1993."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881412.1881445"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536440"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.94"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008684.2008697"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30057-8_1"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4_28"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00116-1"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/233551.233553"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-002-0169-0"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374396"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03356-8_12"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_20"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_6"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_21"},{"key":"e_1_3_2_1_53_1","first-page":"108","volume-title":"Symposium on Logical Foundations of Computer Science","author":"Gurevich Y.","year":"1989","unstructured":"Y. Gurevich and S. Shelah . Nearly linear time. In Logic at Botik '89 , Symposium on Logical Foundations of Computer Science , pages 108 -- 118 , 1989 . Y. Gurevich and S. Shelah. Nearly linear time. In Logic at Botik '89, Symposium on Logical Foundations of Computer Science, pages 108--118, 1989."},{"key":"e_1_3_2_1_55_1","volume-title":"Dec","author":"Harsha P.","year":"2000","unstructured":"P. Harsha and M. Sudan . Small PCPs with low query complexity. Computational Complexity, 9(3--4):157--201 , Dec 2000 . Preliminary version in STACS '91. P. Harsha and M. Sudan. Small PCPs with low query complexity. Computational Complexity, 9(3--4):157--201, Dec 2000. Preliminary version in STACS '91."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/322003.322015"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167244"},{"key":"e_1_3_2_1_58_1","volume-title":"Where delegation meets Einstein","author":"Kalai Y.","year":"2012","unstructured":"Y. Kalai , R. Raz , and R. Rothblum . Where delegation meets Einstein . Isaac Newton Institute for Mathematical Sciences , Formal and Computational Cryptographic Proofs, 2012 . Y. Kalai, R. Raz, and R. Rothblum. Where delegation meets Einstein. Isaac Newton Institute for Mathematical Sciences, Formal and Computational Cryptographic Proofs, 2012."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.84"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217005"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"issue":"4","key":"e_1_3_2_1_62_1","first-page":"175","article-title":"To the definition of an algorithm","volume":"8","author":"Kolmogorov A. N.","year":"1953","unstructured":"A. N. Kolmogorov . To the definition of an algorithm . Uspekhi Matematicheskikh Nauk , 8 ( 4 ): 175 -- 176 , 1953 . A. N. Kolmogorov. To the definition of an algorithm. Uspekhi Matematicheskikh Nauk, 8(4):175--176, 1953.","journal-title":"Uspekhi Matematicheskikh Nauk"},{"issue":"4","key":"e_1_3_2_1_63_1","first-page":"3","article-title":"To the definition of an algorithm","volume":"13","author":"Kolmogorov A. N.","year":"1958","unstructured":"A. N. Kolmogorov and V. A. Uspenskiuii . To the definition of an algorithm . Uspekhi Matematicheskikh Nauk , 13 ( 4 ): 3 -- 28 , 1958 . In Russian. English translation in in AMS Translations, ser. 2, vol. 21 (1963), 217--245. A. N. Kolmogorov and V. A. Uspenskiuii. To the definition of an algorithm. Uspekhi Matematicheskikh Nauk, 13(4):3--28, 1958. In Russian. English translation in in AMS Translations, ser. 2, vol. 21 (1963), 217--245.","journal-title":"Uspekhi Matematicheskikh Nauk"},{"key":"e_1_3_2_1_64_1","volume-title":"Introduction to parallel algorithms and architectures: array, trees, hypercubes","author":"Leighton F. T.","year":"1992","unstructured":"F. T. Leighton . Introduction to parallel algorithms and architectures: array, trees, hypercubes . Morgan Kaufmann Publishers Inc ., San Francisco, CA, USA, 1992 . F. T. Leighton. Introduction to parallel algorithms and architectures: array, trees, hypercubes. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1992."},{"key":"e_1_3_2_1_65_1","volume-title":"Finite Fields","author":"Lidl R.","year":"1997","unstructured":"R. Lidl and H. Niederreiter . Finite Fields . Cambridge University Press , Cambridge, UK , second edition edition, 1997 . R. Lidl and H. Niederreiter. Finite Fields. Cambridge University Press, Cambridge, UK, second edition edition, 1997."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221056"},{"key":"e_1_3_2_1_68_1","volume-title":"Clemson University","author":"Mateer T.","year":"2008","unstructured":"T. Mateer . Fast Fourier Transform algorithms with applications. PhD thesis , Clemson University , 2008 . T. Mateer. Fast Fourier Transform algorithms with applications. PhD thesis, Clemson University, 2008."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.14"},{"key":"e_1_3_2_1_70_1","first-page":"218","volume-title":"CRYPTO '89","author":"Merkle R. C.","year":"1989","unstructured":"R. C. Merkle . A certified digital signature . In CRYPTO '89 , pages 218 -- 238 , 1989 . R. C. Merkle. A certified digital signature. In CRYPTO '89, pages 218--238, 1989."},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/211018.211036"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73011"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1982.1675960"},{"key":"e_1_3_2_1_75_1","first-page":"200","article-title":"A universal automaton","volume":"14","author":"Ofman Y. P.","year":"1965","unstructured":"Y. P. Ofman . A universal automaton . Transactions of the Moscow Mathematical Society , 14 : 200 -- 215 , 1965 . Y. P. Ofman. A universal automaton. Transactions of the Moscow Mathematical Society, 14:200--215, 1965.","journal-title":"Transactions of the Moscow Mathematical Society"},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1971.tb02569.x"},{"key":"e_1_3_2_1_77_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994","unstructured":"C. H. Papadimitriou . Computational Complexity . Addison-Wesley , Reading, MA, USA , 1994 . C. H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, MA, USA, 1994."},{"key":"e_1_3_2_1_78_1","unstructured":"W. J. Paul. Komplexitatstheorie. Teubner Stuttgart Germany 1978.  W. J. Paul. Komplexitatstheorie. Teubner Stuttgart Germany 1978."},{"key":"e_1_3_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.30"},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/322123.322138"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_2_1_82_1","volume-title":"Morgan Kaufman","author":"Reif J. H.","year":"1993","unstructured":"J. H. Reif . Synthesis of parallel algorithms . Morgan Kaufman , San Mateo, CA, USA , 1993 . J. H. Reif. Synthesis of parallel algorithms. Morgan Kaufman, San Mateo, CA, USA, 1993."},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80042-X"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90177-4"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90026-C"},{"key":"e_1_3_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100269"},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322060"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209036"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62231"},{"key":"e_1_3_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/321439.321449"},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_12"}],"event":{"name":"ITCS '13: Innovations in Theoretical Computer Science","location":"Berkeley California USA","acronym":"ITCS '13","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 4th conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422481","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2422436.2422481","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:15Z","timestamp":1750277655000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422481"}},"subtitle":["extended abstract"],"short-title":[],"issued":{"date-parts":[[2013,1,9]]},"references-count":83,"alternative-id":["10.1145\/2422436.2422481","10.1145\/2422436"],"URL":"https:\/\/doi.org\/10.1145\/2422436.2422481","relation":{},"subject":[],"published":{"date-parts":[[2013,1,9]]},"assertion":[{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}