{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:06Z","timestamp":1750694706398,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T00:00:00Z","timestamp":1367366400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001409","name":"Department of Science and Technology, Ministry of Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001409","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["VO 630\/6-2"],"award-info":[{"award-number":["VO 630\/6-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000925","name":"John Templeton Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000925","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2013,5]]},"abstract":"<jats:p>\n            In this paper we initiate the study of proof systems where verification of proofs proceeds by NC\n            <jats:sup>0<\/jats:sup>\n            circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC\n            <jats:sup>0<\/jats:sup>\n            functions. Our results show that the answer to this problem is not determined by the complexity of the language. On the one hand, we construct NC\n            <jats:sup>0<\/jats:sup>\n            proof systems for a variety of languages ranging from regular to NP complete. On the other hand, we show by combinatorial methods that even easy regular languages such as Exact-OR do not admit NC\n            <jats:sup>0<\/jats:sup>\n            proof systems. We also show that Majority does not admit NC\n            <jats:sup>0<\/jats:sup>\n            proof systems. Finally, we present a general construction of NC\n            <jats:sup>0<\/jats:sup>\n            proof systems for regular languages with strongly connected NFA's.\n          <\/jats:p>","DOI":"10.1145\/2462896.2462898","type":"journal-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T16:35:32Z","timestamp":1369758932000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Verifying proofs in constant depth"],"prefix":"10.1145","volume":"5","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[{"name":"Institute for Theoretical Computer Science, Leibniz University, Appelstra\u00dfe, Hannover"}]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, India"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[{"name":"University of T\u00fcbingen, T\u00fcbingen"}]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, India"}]},{"given":"Gido","family":"Scharfenberger-Fabian","sequence":"additional","affiliation":[{"name":"Hochschule F\u00fcr Technik und Wirtschaft, Berlin, Germany"}]},{"given":"Karteek","family":"Sreenivasaiah","sequence":"additional","affiliation":[{"name":"The Institute of Mathematical Sciences, India"}]},{"given":"Michael","family":"Thomas","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Computer Science, Leibniz University, Appelstra\u00dfe, Hannover"}]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Computer Science, Leibniz University, Appelstra\u00dfe, Hannover"}]}],"member":"320","published-online":{"date-parts":[[2013,5,29]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1016\/j.jcss.2010.06.003"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1007\/s00037-001-8191-1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1006\/jcss.1998.1583"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1007\/s00224-009-9172-z"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1137\/S0097539705446950"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1007\/s00037-007-0237-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_7_1","DOI":"10.1007\/s00145-009-9039-0"},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Sciences","volume-title":"Proceedings of the 36th Symposium on Mathematical Foundations of Computer Science","author":"Beyersdorff Olaf","unstructured":"Olaf Beyersdorff , Samir Datta , Meena Mahajan , Gido Scharfenberger-Fabian , Karteek Sreenivasaiah , Michael Thomas , and Heribert Vollmer . 2011a. Verifying proofs in constant depth . In Proceedings of the 36th Symposium on Mathematical Foundations of Computer Science . Lecture Notes in Computer Sciences , vol. 6907 , Springer , Berlin , 84--95. Olaf Beyersdorff, Samir Datta, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, and Heribert Vollmer. 2011a. Verifying proofs in constant depth. In Proceedings of the 36th Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Sciences, vol. 6907, Springer, Berlin, 84--95."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1016\/j.ic.2010.11.006"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1805950.1805952"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1007\/11944836_8"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.2178\/jsl\/1203350791"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.2307\/2273702"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.5555\/645730.668189"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.1145\/1008354.1008356"},{"doi-asserted-by":"publisher","key":"e_1_2_1_16_1","DOI":"10.1145\/1250790.1250855"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1016\/0020-0190(87)90053-6"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1007\/978-3-642-13562-0_4"},{"volume-title":"Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 453--464","author":"Edward","unstructured":"Edward A. Hirsch and Dmitry Itsykson. 2010. On optimal heuristic randomized semidecision procedures, with application to proof complexity . In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 453--464 . Edward A. Hirsch and Dmitry Itsykson. 2010. On optimal heuristic randomized semidecision procedures, with application to proof complexity. In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 453--464.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1002\/rsa.v29:1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1016\/j.apal.2008.09.017"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.2178\/bsl\/1203350879"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1109\/FOCS.2011.20"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1137\/100814998"},{"volume-title":"Introduction to Circuit Complexity -- A Uniform Approach","author":"Vollmer Heribert","unstructured":"Heribert Vollmer . 1999. Introduction to Circuit Complexity -- A Uniform Approach . Springer , Berlin . Heribert Vollmer. 1999. Introduction to Circuit Complexity -- A Uniform Approach. Springer, Berlin.","key":"e_1_2_1_25_1"},{"volume-title":"The Complexity of Boolean Functions","author":"Wegener Ingo","unstructured":"Ingo Wegener . 1987. The Complexity of Boolean Functions . B. G. Teubner & John Wiley , Stuttgart . Ingo Wegener. 1987. The Complexity of Boolean Functions. B. G. Teubner & John Wiley, Stuttgart.","key":"e_1_2_1_26_1"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462896.2462898","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2462896.2462898","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:36Z","timestamp":1750236516000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2462896.2462898"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["10.1145\/2462896.2462898"],"URL":"https:\/\/doi.org\/10.1145\/2462896.2462898","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2013,5]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}