{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:10:51Z","timestamp":1725567051448},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_35","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"339-348","source":"Crossref","is-referenced-by-count":2,"title":["A Note on Zero Error Algorithms Having Oracle Access to One NP Query"],"prefix":"10.1007","author":[{"given":"Jin-Yi","family":"Cai","sequence":"first","affiliation":[]},{"given":"Venkatesan T.","family":"Chakaravarthy","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"35_CR1","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences\u00a036(2), 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"35_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"R. Boppana","year":"1987","unstructured":"Boppana, R., 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"},{"key":"35_CR3","unstructured":"Cai, J.: Sp 2 \u2286 ZPPNP. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (2001)"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Cai, J., Chakaravarthy, V., Hemaspaandra, L., Ogihara, M.: Competing provers yield improved Karp\u2013Lipton collapse results. In: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (2003)","DOI":"10.1007\/3-540-36494-3_47"},{"issue":"5","key":"35_CR5","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(96)00016-6","volume":"57","author":"R. Canetti","year":"1996","unstructured":"Canetti, R.: More on BPP and the polynomial-time hierarchy. Information Processing Letters\u00a057(5), 237\u2013241 (1996)","journal-title":"Information Processing Letters"},{"key":"35_CR6","unstructured":"Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the complexity of succinct zero-sum games. Technical Report TR04\u2013001, Electronic Colloquium on Computational Complexity (2004), Available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"35_CR7","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Pavan, A., Sengupta, S.: Proving SAT does not have small circuits with an application to the two queries problem. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity (2003)","DOI":"10.1109\/CCC.2003.1214433"},{"key":"35_CR8","unstructured":"Goldreich, O., Zuckerman, D.: Another proof that BPP PH (and more). Technical Report TR97\u2013045, Electronic Colloquium on Computational Complexity (1997), Available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"35_CR9","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: Proceedings of the 18th ACM Symposium on Theory of Computing (1986)","DOI":"10.1145\/12130.12137"},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P=BPP unless E has subexponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th ACM Symposium on Theory of Computing (1997)","DOI":"10.1145\/258533.258590"},{"issue":"5","key":"35_CR11","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial hierarchy collapses. SIAM Journal on Computing\u00a031(5), 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"35_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","volume":"17","author":"C. Lautemann","year":"1982","unstructured":"Lautemann, C.: BPP and the polynomial hierarchy. Information Processing Letters\u00a017(4), 215\u2013217 (1982)","journal-title":"Information Processing Letters"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Miltersen, P., Vinodchandran, N.: Derandomizing Arthur-Merlin games using hitting sets. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science (1999)","DOI":"10.1109\/SFFCS.1999.814579"},{"issue":"2","key":"35_CR14","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. Journal of Computer and System Sciences\u00a049(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"35_CR15","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/s000370050007","volume":"7","author":"A. Russell","year":"1998","unstructured":"Russell, A., Sundaram, R.: Symmetric alternation captures BPP. Computational Complexity\u00a07(2), 152\u2013162 (1998)","journal-title":"Computational Complexity"},{"key":"35_CR16","unstructured":"Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. Technical Report TR04\u2013086, Electronic Colloquium on Computational Complexity (2004), Available at http:\/\/www.eccc.uni-trier.de\/eccc"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"Sipser, M.: A complexity theoretic approach to randomness. In: Proceedings of the 15th ACM Symposium on Theory of Computing (1983)","DOI":"10.1145\/800061.808762"},{"issue":"4\/5","key":"35_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01940870","volume":"16","author":"D. Zuckerman","year":"1996","unstructured":"Zuckerman, D.: Simulating BPP using a general weak random source. Algorithmica\u00a016(4\/5), 367\u2013391 (1996)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T22:36:50Z","timestamp":1586471810000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11533719_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}