{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:04Z","timestamp":1759638364494,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2008,5,17]],"date-time":"2008-05-17T00:00:00Z","timestamp":1210982400000},"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":[[2008,5,17]]},"DOI":"10.1145\/1374376.1374399","type":"proceedings-article","created":{"date-parts":[[2008,5,28]],"date-time":"2008-05-28T16:50:20Z","timestamp":1211993420000},"page":"143-152","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["A (de)constructive approach to program checking"],"prefix":"10.1145","author":[{"given":"Shafi","family":"Goldwasser","sequence":"first","affiliation":[{"name":"MIT and Weizmann Institute, Cambridge and Rehovot, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Gutfreund","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Healy","sequence":"additional","affiliation":[{"name":"Harvard University, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tali","family":"Kaufman","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy N.","family":"Rothblum","sequence":"additional","affiliation":[{"name":"MIT, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,5,17]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_2_1_2_1","first-page":"2","article-title":"The query complexity of program checking by constant-depth circuits","author":"Arvind V.","year":"2002","unstructured":"V. Arvind , K. Subrahmanyam , and N. Vinodchandran . The query complexity of program checking by constant-depth circuits . Chicago Journal of Theoretical Computer Science , 2 , 2002 . V. Arvind, K. Subrahmanyam, and N. Vinodchandran. The query complexity of program checking by constant-depth circuits. Chicago Journal of Theoretical Computer Science, 2, 2002.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89520"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275486"},{"key":"e_1_3_2_1_5_1","first-page":"194","volume-title":"RANDOM","author":"Barak B.","year":"2002","unstructured":"B. Barak . A probabilistic-time hierarchy theorem for \"slightly non-uniform\" algorithms . In RANDOM , pages 194 -- 208 , 2002 . B. Barak. A probabilistic-time hierarchy theorem for \"slightly non-uniform\" algorithms. In RANDOM, pages 194--208, 2002."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185343"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_25"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28396"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195408"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.33"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060642"},{"key":"e_1_3_2_1_15_1","first-page":"57","article-title":"Fast probablistic algorithms. Springer Verlag Lecture Notes in CS","volume":"74","author":"Freivalds R.","year":"1979","unstructured":"R. Freivalds . Fast probablistic algorithms. Springer Verlag Lecture Notes in CS , Mathematical Foundations of CS , 74 : 57 -- 69 , 1979 . R. Freivalds. Fast probablistic algorithms. Springer Verlag Lecture Notes in CS, Mathematical Foundations of CS, 74:57--69, 1979.","journal-title":"Mathematical Foundations of CS"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250855"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0178-7"},{"key":"e_1_3_2_1_20_1","first-page":"1","volume-title":"CCC","author":"Impagliazzo R.","year":"2001","unstructured":"R. Impagliazzo , V. Kabanets , and A. Wigderson . In search of an easy witness: Exponential time vs. probabilistic polynomial time . In CCC , pages 1 -- 11 , 2001 . R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. In CCC, pages 1--11, 2001."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/646255.684418"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62215"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/002\/13"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01961540"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250832"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250854"},{"key":"e_1_3_2_1_28_1","first-page":"11","volume-title":"FOCS","author":"Shamir A.","year":"1990","unstructured":"A. Shamir . IP = PSPACE. In FOCS , pages 11 -- 15 , 1990 . A. Shamir. IP = PSPACE. In FOCS, pages 11--15, 1990."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/872747.873197"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/268999.269003"}],"event":{"name":"STOC '08: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Victoria British Columbia Canada","acronym":"STOC '08"},"container-title":["Proceedings of the fortieth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374399","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1374376.1374399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:32Z","timestamp":1750278152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1374376.1374399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,17]]},"references-count":28,"alternative-id":["10.1145\/1374376.1374399","10.1145\/1374376"],"URL":"https:\/\/doi.org\/10.1145\/1374376.1374399","relation":{},"subject":[],"published":{"date-parts":[[2008,5,17]]},"assertion":[{"value":"2008-05-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}