{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:23:14Z","timestamp":1758273794904},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662444641"},{"type":"electronic","value":"9783662444658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44465-8_3","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:33:02Z","timestamp":1407839582000},"page":"25-32","source":"Crossref","is-referenced-by-count":4,"title":["Zero Knowledge and Circuit Minimization"],"prefix":"10.1007","author":[{"given":"Eric","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bireswar","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"1467","DOI":"10.1137\/050628994","volume":"35","author":"E. Allender","year":"2006","unstructured":"Allender, E., Buhrman, H., Kouck\u00fd, M., van Melkebeek, D., Ronneburger, D.: Power from random strings. SIAM Journal on Computing\u00a035, 1467\u20131493 (2006)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"3_CR2","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/s00224-007-9028-3","volume":"43","author":"V. Arvind","year":"2008","unstructured":"Arvind, V., Das, B.: SZK proofs for black-box group problems. Theory Comput. Syst.\u00a043(2), 100\u2013117 (2008)","journal-title":"Theory Comput. Syst."},{"key":"3_CR3","unstructured":"Arvind, V., Tor\u00e1n, J.: Isomorphism testing: Perspective and open problems. Bulletin of the EATCS\u00a086 (2005)"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R.B. Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Information Processing Letters\u00a025(2), 127\u2013132 (1987)","journal-title":"Information Processing Letters"},{"issue":"2","key":"3_CR5","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00145-002-0113-0","volume":"16","author":"M. Ben-Or","year":"2003","unstructured":"Ben-Or, M., Gutfreund, D.: Trading help for interaction in statistical zero-knowledge proofs. J. Cryptology\u00a016(2), 95\u2013116 (2003)","journal-title":"J. Cryptology"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-540-78524-8_28","volume-title":"Theory of Cryptography","author":"A. Chailloux","year":"2008","unstructured":"Chailloux, A., Ciocan, D.F., Kerenidis, I., Vadhan, S.P.: Interactive and noninteractive zero knowledge are equivalent in the help model. In: Canetti, R. (ed.) TCC 2008. LNCS, vol.\u00a04948, pp. 501\u2013534. Springer, Heidelberg (2008)"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: ACM Symposium on Theory of Computing (STOC), pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"issue":"3","key":"3_CR8","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. Journal of the ACM\u00a038(3), 691\u2013729 (1991)","journal-title":"Journal of the ACM"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J., Impagliazzo, R., Levin, L., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing\u00a028, 1364\u20131396 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Kabanets, V., Cai, J.-Y.: Circuit minimization problem. In: ACM Symposium on Theory of Computing (STOC), pp. 73\u201379 (2000)","DOI":"10.1145\/335305.335314"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-540-73420-8_30","volume-title":"Automata, Languages and Programming","author":"B. Kapron","year":"2007","unstructured":"Kapron, B., Malka, L., Srinivasan, V.: A characterization of non-interactive instance-dependent commitment-schemes (NIC). In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 328\u2013339. Springer, Heidelberg (2007)"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J.: Forcing with Random Variables and Proof Complexity. Cambridge University Press (2011)","DOI":"10.1017\/CBO9781139107211"},{"key":"3_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"J. K\u00f6bler","year":"1993","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The Graph Isomorphism Problem: Its Structural Complexity. Birkhauser Verlag, Basel (1993)"},{"key":"3_CR14","first-page":"265","volume":"9","author":"L.A. Levin","year":"1973","unstructured":"Levin, L.A.: Universal sequential search problems. Problems of Information Transmission\u00a09, 265\u2013266 (1973)","journal-title":"Problems of Information Transmission"},{"key":"3_CR15","unstructured":"Levin, L.: Personal communication (2003)"},{"key":"3_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139164849","volume-title":"Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica","author":"S. Pemmaraju","year":"2003","unstructured":"Pemmaraju, S., Skiena, S.: Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press, New York (2003)"},{"key":"3_CR17","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A. Razborov","year":"1997","unstructured":"Razborov, A., Rudich, S.: Natural proofs. Journal of Computer and System Sciences\u00a055, 24\u201335 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"3_CR18","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/MAHC.1984.10036","volume":"6","author":"B.A. Trakhtenbrot","year":"1984","unstructured":"Trakhtenbrot, B.A.: A survey of Russian approaches to perebor (brute-force searches) algorithms. IEEE Annals of the History of Computing\u00a06(4), 384\u2013400 (1984)","journal-title":"IEEE Annals of the History of Computing"},{"issue":"6","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1297","DOI":"10.1142\/S0129054105003819","volume":"16","author":"V.N. Variyam","year":"2005","unstructured":"Variyam, V.N.: Nondeterministic circuit minimization problem and derandomizing Arthur-Merlin games. Int. J. Found. Comput. Sci.\u00a016(6), 1297\u20131308 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR20","unstructured":"Wikipedia (2014), http:\/\/en.wikipedia.org\/wiki\/NP-intermediate"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44465-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,15]],"date-time":"2023-07-15T22:04:15Z","timestamp":1689458655000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44465-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662444641","9783662444658"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44465-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}