{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T21:13:13Z","timestamp":1672607593010},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,7,23]],"date-time":"2008-07-23T00:00:00Z","timestamp":1216771200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00224-008-9126-x","type":"journal-article","created":{"date-parts":[[2008,7,22]],"date-time":"2008-07-22T17:40:48Z","timestamp":1216748448000},"page":"193-221","source":"Crossref","is-referenced-by-count":3,"title":["The 1-Versus-2 Queries Problem Revisited"],"prefix":"10.1007","volume":"46","author":[{"given":"Rahul","family":"Tripathi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,7,23]]},"reference":[{"issue":"1","key":"9126_CR1","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0890-5401(03)00091-9","volume":"186","author":"A. Amir","year":"2003","unstructured":"Amir, A., Beigel, R., Gasarch, W.: Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186(1), 104\u2013139 (2003)","journal-title":"Inf. Comput."},{"issue":"3","key":"9126_CR2","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 52(3), 421\u2013433 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9126_CR3","doi-asserted-by":"crossref","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. Math. Syst. Theory 26(3), 293\u2013310 (1993)","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"9126_CR4","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1006\/jcss.1999.1647","volume":"59","author":"H. Buhrman","year":"1999","unstructured":"Buhrman, H., Fortnow, L.: Two queries. J. Comput. Syst. Sci. 59(2), 182\u2013194 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9126_CR5","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/j.jcss.2003.07.015","volume":"73","author":"J. Cai","year":"2007","unstructured":"Cai, J.: S 2 p \u2286ZPPNP. J. Comput. Syst. Sci. 73(1), 25\u201335 (2007)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9126_CR6","doi-asserted-by":"crossref","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. Inf. Process. Lett. 57(5), 237\u2013241 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9126_CR7","doi-asserted-by":"crossref","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. J. Comb. Optim. 11(2), 189\u2013202 (2006)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"9126_CR8","doi-asserted-by":"crossref","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. Inf. Comput. 198(1), 1\u201323 (2005)","journal-title":"Inf. Comput."},{"issue":"6","key":"9126_CR9","doi-asserted-by":"crossref","first-page":"1232","DOI":"10.1137\/0217078","volume":"17","author":"J. Cai","year":"1988","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy I: Structural properties. SIAM J. Comput. 17(6), 1232\u20131252 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9126_CR10","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1137\/0218007","volume":"18","author":"J. Cai","year":"1989","unstructured":"Cai, J., Gundermann, T., Hartmanis, J., Hemachandra, L., Sewelson, V., Wagner, K., Wechsung, G.: The boolean hierarchy II: Applications. SIAM J. Comput. 18(1), 95\u2013111 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9126_CR11","doi-asserted-by":"crossref","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. Math. Syst. Theory 28(3), 173\u2013198 (1995)","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"9126_CR12","doi-asserted-by":"crossref","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 J. Comput. 25(2), 340\u2013354 (1996)","journal-title":"SIAM J. Comput."},{"key":"9126_CR13","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 Comput. Soc., Los Alamitos (2007)"},{"key":"9126_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1007\/11672142_18","volume-title":"Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science","author":"V. Chakaravarthy","year":"2006","unstructured":"Chakaravarthy, V., Roy, S.: Oblivious symmetric alternation. In: Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 3884, pp. 230\u2013241. Springer, Berlin (2006)"},{"key":"9126_CR15","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the complexity of succinct zero-sum games. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pp. 323\u2013332 (2005). To appear in Comput. Complex.","DOI":"10.1109\/CCC.2005.18"},{"issue":"3","key":"9126_CR16","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1016\/j.jcss.2007.06.017","volume":"74","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Pavan, A., Sengupta, S.: Proving SAT does not have small circuits with an application to the two queries problem. J. Comput. Syst. Sci. 74(3), 358\u2013363 (2008)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9126_CR17","doi-asserted-by":"crossref","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 J. Comput. 28(2), 383\u2013393 (1998)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9126_CR18","doi-asserted-by":"crossref","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+1 queries. SIAM J. Comput. 34(6), 1352\u20131369 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9126_CR19","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1142\/S012905419300016X","volume":"4","author":"L. Hemaspaandra","year":"1993","unstructured":"Hemaspaandra, L., Jain, S., Vereshchagin, N.: Banishing robust Turing completeness. Int. J. Found. Comput. Sci. 4(3), 245\u2013265 (1993)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"9126_CR20","doi-asserted-by":"crossref","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 J. Comput. 17(6), 1263\u20131282 (1988). Erratum appears in the same journal, 20(2), 404","journal-title":"SIAM J. Comput."},{"key":"9126_CR21","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. Assoc. Comput. Mach., New York (1980)"},{"issue":"3","key":"9126_CR22","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 36(3), 490\u2013509 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"9126_CR23","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":"9126_CR24","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/s000370050007","volume":"7","author":"A. Russell","year":"1998","unstructured":"Russell, A., Sundaram, R.: Symmetric alternation captures BPP. Comput. Complex. 7(2), 152\u2013162 (1998)","journal-title":"Comput. Complex."},{"key":"9126_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/BFb0012797","volume-title":"Proceedings of the 9th International Colloquium on Automata, Languages, and Programming","author":"M. Sipser","year":"1982","unstructured":"Sipser, M.: On relativization and the existence of complete sets. In: Proceedings of the 9th International Colloquium on Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 140, pp. 523\u2013531. Springer, Berlin (1982)"},{"key":"9126_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-540-77120-3_14","volume-title":"Proceedings of the 18th International Symposium on Algorithms and Computation","author":"R. Tripathi","year":"2007","unstructured":"Tripathi, R.: The 1-versus-2 queries problem revisited. In: Proceedings of the 18th International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol. 4835, pp. 137\u2013147. Springer, Berlin (2007)"},{"key":"9126_CR27","unstructured":"Wagner, K.: Number-of-query hierarchies. Technical Report 4, Institut f\u00fcr Informatik, Universit\u00e4t W\u00fcrzburg, W\u00fcrzburg, Germany, February 1989"},{"issue":"3","key":"9126_CR28","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 26(3), 287\u2013300 (1983)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9126-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9126-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9126-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:36Z","timestamp":1558698696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9126-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7,23]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9126"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9126-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7,23]]}}}