{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:47:36Z","timestamp":1725497256805},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_14","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T06:31:09Z","timestamp":1196922669000},"page":"137-147","source":"Crossref","is-referenced-by-count":2,"title":["The 1-Versus-2 Queries Problem Revisited"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Tripathi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"14_CR1","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"Bshouty, N., Cleve, R., Gavald\u00e0, R., Kannan, S., Tamon, C.: Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences\u00a052(3), 421\u2013433 (1996)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"14_CR2","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF01371729","volume":"26","author":"R. Beigel","year":"1993","unstructured":"Beigel, R., Chang, R., Ogiwara, M.: A relationship between difference hierarchies and relativized polynomial hierarchies. Mathematical Systems Theory\u00a026(3), 293\u2013310 (1993)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"14_CR3","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1006\/jcss.1999.1647","volume":"59","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., Fortnow, L.: Two queries. Journal of Computer and System Sciences\u00a059(2), 182\u2013194 (1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"14_CR4","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.jcss.2003.07.015","volume":"73","author":"J. Cai","year":"2007","unstructured":"Cai, J.: S\n                    \n                      \n                    \n                    $_{2}^{p}$\n                   is subset of ZPPNP. Journal of Computer and System Sciences\u00a073(1), 25\u201335 (2007)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"14_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"},{"issue":"2","key":"14_CR6","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10878-006-7130-0","volume":"11","author":"J. Cai","year":"2006","unstructured":"Cai, J., Chakaravarthy, V.: On zero error algorithms having oracle access to one query. Journal of Combinatorial Optimization\u00a011(2), 189\u2013202 (2006)","journal-title":"Journal of Combinatorial Optimization"},{"issue":"1","key":"14_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2005.01.002","volume":"198","author":"J. Cai","year":"2005","unstructured":"Cai, J., Chakaravarthy, V., Hemaspaandra, L., Ogihara, M.: Competing provers yield improved Karp-Lipton collapse results. Information and Computation\u00a0198(1), 1\u201323 (2005)","journal-title":"Information and Computation"},{"issue":"3","key":"14_CR8","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01303054","volume":"28","author":"R. Chang","year":"1995","unstructured":"Chang, R., Kadin, J.: On computing boolean connectives of characteristic functions. Mathematical Systems Theory\u00a028(3), 173\u2013198 (1995)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"14_CR9","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539790178069","volume":"25","author":"R. Chang","year":"1996","unstructured":"Chang, R., Kadin, J.: The boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing\u00a025(2), 340\u2013354 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"14_CR10","first-page":"52","volume-title":"Proceedings of the 22nd Annual IEEE Conference on Computational Complexity","author":"R. Chang","year":"2007","unstructured":"Chang, R., Purini, S.: Bounded queries and the NP machine hypothesis. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pp. 52\u201359. IEEE Computer Society Press, June (2007)"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1007\/11672142_18","volume-title":"STACS 2006","author":"V. Chakaravarthy","year":"2006","unstructured":"Chakaravarthy, V., Roy, S.: Oblivious symmetric alternation. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 230\u2013241. Springer, Heidelberg (2006)"},{"key":"14_CR12","unstructured":"Fortnow, L., Pavan, A., Sengupta, S.: Proving SAT does not have small circuits with an application to the two queries problem. Journal of Computer and System Sciences (to appear)"},{"issue":"2","key":"14_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1137\/S0097539796306474","volume":"28","author":"E. Hemaspaandra","year":"1998","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Hempel, H.: A downward collapse within the polynomial hierarchy. SIAM Journal on Computing\u00a028(2), 383\u2013393 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"14_CR14","doi-asserted-by":"publisher","first-page":"1352","DOI":"10.1137\/S0097539701391002","volume":"34","author":"E. Hemaspaandra","year":"2005","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Hempel, H.: Extending downward collapse from 1-versus-2 queries to m-versus-m\u2009+\u20091 queries. SIAM Journal on Computing\u00a034(6), 1352\u20131369 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"14_CR15","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0217080","volume":"17","author":"J. Kadin","year":"1988","unstructured":"Kadin, J.: The polynomial time hierarchy collapses if the boolean hierarchy collapses. SIAM Journal on Computing\u00a017(6), 1263\u20131282 (1988) Erratum appears in the same journal 20(2) 404","journal-title":"SIAM Journal on Computing"},{"key":"14_CR16","first-page":"302","volume-title":"Proceedings of the 12th ACM Symposium on Theory of Computing","author":"R. Karp","year":"1980","unstructured":"Karp, R., Lipton, R.: Some connections between nonuniform and uniform complexity classes. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 302\u2013309. ACM Press, New York (1980)"},{"issue":"3","key":"14_CR17","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. Krentel","year":"1988","unstructured":"Krentel, M.: The complexity of optimization problems. Journal of Computer and System Sciences\u00a036(3), 490\u2013509 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Pavan, A., Santhanam, R., Vinodchandran, N.: Some results on average-case hardness within the polynomial hierarchy. In: Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science, pp. 188\u2013199 (2006)","DOI":"10.1007\/11944836_19"},{"issue":"2","key":"14_CR19","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":"14_CR20","unstructured":"Wagner, K.: Number-of-query hierarchies. Technical Report\u00a04, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, Germany (February 1989)"},{"key":"14_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(83)90020-8","volume":"26","author":"C. Yap","year":"1983","unstructured":"Yap, C.: Some consequences of non-uniform conditions on uniform classes. Theoretical Computer Science\u00a026, 287\u2013300 (1983)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:01:02Z","timestamp":1619506862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_14","relation":{},"subject":[]}}