{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:25:00Z","timestamp":1725600300752},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229923"},{"type":"electronic","value":"9783642229930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_11","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"84-95","source":"Crossref","is-referenced-by-count":1,"title":["Verifying Proofs in Constant Depth"],"prefix":"10.1007","author":[{"given":"Olaf","family":"Beyersdorff","sequence":"first","affiliation":[]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[]},{"given":"Meena","family":"Mahajan","sequence":"additional","affiliation":[]},{"given":"Gido","family":"Scharfenberger-Fabian","sequence":"additional","affiliation":[]},{"given":"Karteek","family":"Sreenivasaiah","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Thomas","sequence":"additional","affiliation":[]},{"given":"Heribert","family":"Vollmer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"11_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.jcss.2010.06.003","volume":"77","author":"M. Agrawal","year":"2010","unstructured":"Agrawal, M.: The isomorphism conjecture for constant depth reductions. Journal of Computer and System Sciences\u00a077(1), 3\u201313 (2010)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"11_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s00037-001-8191-1","volume":"10","author":"M. Agrawal","year":"2001","unstructured":"Agrawal, M., Allender, E., Impagliazzo, R., Pitassi, T., Rudich, S.: Reducing the complexity of reductions. Computational Complexity\u00a010(2), 117\u2013138 (2001)","journal-title":"Computational Complexity"},{"issue":"2","key":"11_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M. Agrawal","year":"1998","unstructured":"Agrawal, M., Allender, E., Rudich, S.: Reductions in circuit complexity: An isomorphism theorem and a gap theorem. J. Comput. Syst. Sci.\u00a057(2), 127\u2013143 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"11_CR4","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B. Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM J. Comput.\u00a036(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00037-007-0237-6","volume":"17","author":"B. Applebaum","year":"2008","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. Computational Complexity\u00a017(1), 38\u201369 (2008)","journal-title":"Computational Complexity"},{"issue":"4","key":"11_CR6","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s00145-009-9039-0","volume":"22","author":"B. Applebaum","year":"2009","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography with constant input locality. J. Cryptology\u00a022(4), 429\u2013469 (2009)","journal-title":"J. Cryptology"},{"issue":"3","key":"11_CR7","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.ic.2010.11.006","volume":"209","author":"O. Beyersdorff","year":"2011","unstructured":"Beyersdorff, O., K\u00f6bler, J., M\u00fcller, S.: Proof systems that take advice. Information and Computation\u00a0209(3), 320\u2013332 (2011)","journal-title":"Information and Computation"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Beyersdorff, O., M\u00fcller, S.: A tight Karp-Lipton collapse result in bounded arithmetic. ACM Transactions on Computational Logic\u00a011(4) (2010)","DOI":"10.1145\/1805950.1805952"},{"issue":"4","key":"11_CR9","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.2178\/jsl\/1203350791","volume":"72","author":"S.A. Cook","year":"2007","unstructured":"Cook, S.A., Kraj\u00ed\u010dek, J.: Consequences of the provability of NP \u2286 P\/poly. The Journal of Symbolic Logic\u00a072(4), 1353\u20131371 (2007)","journal-title":"The Journal of Symbolic Logic"},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"Cook, S.A., Reckhow, R.A.: The relative efficiency of propositional proof systems. The Journal of Symbolic Logic\u00a044(1), 36\u201350 (1979)","journal-title":"The Journal of Symbolic Logic"},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC0. In: Proc. 26th Symposium on Mathematical Foundations of Computer Science, pp. 272\u2013284 (2001)","DOI":"10.1007\/3-540-44683-4_24"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: Verifying and decoding in constant depth. In: Proc.39th ACM Symposium on Theory of Computing, pp. 440\u2013449 (2007)","DOI":"10.1145\/1250790.1250855"},{"issue":"3","key":"11_CR13","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(87)90053-6","volume":"26","author":"J. H\u00e5stad","year":"1987","unstructured":"H\u00e5stad, J.: One-way permutations in NC0. Inf. Process. Lett.\u00a026(3), 153\u2013155 (1987)","journal-title":"Inf. Process. Lett."},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-642-13562-0_4","volume-title":"Theory and Applications of Models of Computation","author":"E.A. Hirsch","year":"2010","unstructured":"Hirsch, E.A.: Optimal Acceptors and Optimal Proof Systems. In: Kratochv\u00edl, J., Li, A., Fiala, J., Kolman, P. (eds.) TAMC 2010. LNCS, vol.\u00a06108, pp. 28\u201339. Springer, Heidelberg (2010)"},{"key":"11_CR15","unstructured":"Hirsch, E.A., Itsykson, D.: Hirsch and Dmitry Itsykson. On optimal heuristic randomized semidecision procedures, with application to proof complexity. In: Proc. 27th Symposium on Theoretical Aspects of Computer Science, pp. 453\u2013464 (2010)"},{"issue":"1","key":"11_CR16","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"E. Mossel","year":"2006","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On \u03b5-biased generators in NC0. Random Struct. Algorithms\u00a029(1), 56\u201381 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"11_CR17","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.apal.2008.09.017","volume":"157","author":"P. Pudl\u00e1k","year":"2009","unstructured":"Pudl\u00e1k, P.: Quantum deduction rules. Annals of Pure and Applied Logic\u00a0157(1), 16\u201329 (2009)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"4","key":"11_CR18","doi-asserted-by":"publisher","first-page":"417","DOI":"10.2178\/bsl\/1203350879","volume":"13","author":"N. Segerlind","year":"2007","unstructured":"Segerlind, N.: The complexity of propositional proofs. Bulletin of Symbolic Logic\u00a013(4), 417\u2013481 (2007)","journal-title":"Bulletin of Symbolic Logic"},{"key":"11_CR19","series-title":"Texts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to Circuit Complexity \u2013 A Uniform Approach","author":"H. Vollmer","year":"1999","unstructured":"Vollmer, H.: Introduction to Circuit Complexity \u2013 A Uniform Approach. Texts in Theoretical Computer Science. Springer, Heidelberg (1999)"},{"key":"11_CR20","series-title":"Wiley-Teubner series in computer science","volume-title":"The Complexity of Boolean Functions","author":"I. Wegener","year":"1987","unstructured":"Wegener, I.: The Complexity of Boolean Functions. Wiley-Teubner series in computer science. B. G. Teubner & John Wiley, Stuttgart (1987)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T11:40:20Z","timestamp":1620042020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}