{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T21:40:09Z","timestamp":1743975609098,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":47,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642322402"},{"type":"electronic","value":"9783642322419"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32241-9_40","type":"book-chapter","created":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T15:12:12Z","timestamp":1344870732000},"page":"470-481","source":"Crossref","is-referenced-by-count":0,"title":["On the Advice Complexity of Tournaments"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Ben Daniel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"40_CR1","doi-asserted-by":"crossref","unstructured":"Althfer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications\u00a0199(Suppl. 1), 339\u2013355 (1994); Special Issue Honoring Ingram Olkin","DOI":"10.1016\/0024-3795(94)90357-3"},{"key":"40_CR2","unstructured":"Amir, A., Beigel, R., Gasarch, W.I.: Some connections between bounded query classes and non-uniform complexity. ECCC\u00a07(024) (2000)"},{"key":"40_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. In: Proc. of the 31st IEEE Symp. on Foundations of Computer Science, pp. 16\u201325 (1990)","DOI":"10.1109\/FSCS.1990.89520"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1137\/0215053","volume":"15","author":"J. Balc\u00e1zar","year":"1986","unstructured":"Balc\u00e1zar, J., Book, R.V., Sch\u00f6ning, U.: Sparse sets lowness and highness. SIAM J. Comput.\u00a015, 739\u2013747 (1986)","journal-title":"SIAM J. Comput."},{"key":"40_CR5","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1145\/5925.5937","volume":"33","author":"J.L. Balc\u00e1zar","year":"1986","unstructured":"Balc\u00e1zar, J.L., Book, R.V., Sch\u00f6ning, U.: The polynomial-time hierarchy and sparse oracles. J. ACM\u00a033, 603\u2013617 (1986)","journal-title":"J. ACM"},{"key":"40_CR6","unstructured":"Beigel, R.: Personal communication. Weak Approximation, Help Bits, and the Complexity of Optimization Problems (2005)"},{"key":"40_CR7","unstructured":"Beigel, R., Fortnow, L., Pavan, A.: Membership comparable and P-selective sets. Technical Report 2002-006N. NEC Research Institute (2008)"},{"key":"40_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-14165-2_39","volume-title":"Automata, Languages and Programming","author":"A. Beimel","year":"2010","unstructured":"Beimel, A., Ben Daniel, S.A., Kushilevitz, E., Weinreb, E.: Choosing, Agreeing, and Eliminating in Communication Complexity. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 451\u2013462. Springer, Heidelberg (2010)"},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Bogdanov, A., Safra, S.: Hardness amplification for errorless heuristics. In: Annual IEEE Symposium on Foundations of Computer Science, vol.\u00a00, pp. 418\u2013426 (2007)","DOI":"10.1109\/FOCS.2007.25"},{"issue":"2","key":"40_CR10","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1006\/jcss.1996.0062","volume":"53","author":"H. Buhrman","year":"1996","unstructured":"Buhrman, H., Torenvliet, L.: P-selective self-reducible sets: A new characterization of p. J. Comput. Syst. Sci.\u00a053(2), 210\u2013217 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"40_CR11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/0020-0190(93)90146-Z","volume":"48","author":"H. Buhrman","year":"1993","unstructured":"Buhrman, H., Torenvliet, L., van Emde Boas, P.: Twenty questions to a P-selector. Inf. Process. Lett.\u00a048(4), 201\u2013204 (1993)","journal-title":"Inf. Process. Lett."},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"Buhrman, H., van Helden, P., Torenvliet, L.: P-selective self-reducibles sets: a new characterization of p. In: Proceedings of the Eighth Annual Structure in Complexity Theory Conference 1993, pp. 44\u201351, 18\u201321 (1993)","DOI":"10.1109\/SCT.1993.336542"},{"key":"40_CR13","unstructured":"Buresh-Oppenheim, J., Kabanets, V., Santhanam, R.: Uniform hardness amplification in NP via monotone codes. Electronic Colloquium on Computational Complexity (ECCC)\u00a013(154) (2006)"},{"key":"40_CR14","unstructured":"Cai, J., Chakaravarthy, V., Hemaspaandra, L., Ogihara, M.: Some Karp-Lipton type theorems based on S 2 Technical Report TR-819, Department of Computer Science, University of Rochester, Rochester, NY (2001)"},{"issue":"4","key":"40_CR15","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\u00edcek, J.: Consequences of the provability of NP subset of or equal to P\/poly. J. Symb. Log.\u00a072(4), 1353\u20131371 (2007)","journal-title":"J. Symb. Log."},{"key":"40_CR16","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/1122480.1122495","volume":"37","author":"P. Faliszewski","year":"2006","unstructured":"Faliszewski, P., Hemaspaandra, L.: Open questions in the theory of semifeasible computation. SIGACT News\u00a037, 47\u201365 (2006)","journal-title":"SIGACT News"},{"issue":"5","key":"40_CR17","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1142\/S0129054105003376","volume":"16","author":"P. Faliszewski","year":"2005","unstructured":"Faliszewski, P., Hemaspaandra, L.A.: Advice for semifeasible sets and the complexity-theoretic cost(lessness) of algebraic properties. Int. J. Found. Comput. Sci.\u00a016(5), 913\u2013928 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Guruswami, V.: Hardness amplification within NP against deterministic algorithms. In: Annual IEEE Conference on Computational Complexity, vol.\u00a00, pp. 19\u201330 (2008)","DOI":"10.1109\/CCC.2008.17"},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Transactions of the American Mathematical Society\u00a0117, 285\u2013306 (1965)","journal-title":"Transactions of the American Mathematical Society"},{"key":"40_CR20","unstructured":"Hemaspaandra, E., Naik, A.V., Ogihara, M., Selman, A.L.: P-selective sets, and reducing search to decision vs. self-reducibility (1994)"},{"issue":"4","key":"40_CR21","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S0097539794268315","volume":"25","author":"L.A. Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, L.A., Naik, A.V., Ogihara, M., Selman, A.L.: Computing solutions uniquely collapses the polynomial hierarchy. SIAM J. Comput.\u00a025(4), 697\u2013708 (1996)","journal-title":"SIAM J. Comput."},{"issue":"8","key":"40_CR22","first-page":"670","volume":"4","author":"L.A. Hemaspaandra","year":"1998","unstructured":"Hemaspaandra, L.A., Nasipak, C., Parkins, K.: A note on linear nondeterminism, linear-sized, Karp-Lipton advice for the P-selective sets. JJUCS\u00a04(8), 670\u2013674 (1998)","journal-title":"JJUCS"},{"issue":"2","key":"40_CR23","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0304-3975(95)00076-3","volume":"154","author":"L.A. Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, L.A., Torenvliet, L.: Optimal advice. Theoretical Computer Science\u00a0154(2), 367\u2013377 (1996)","journal-title":"Theoretical Computer Science"},{"key":"40_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05080-4","volume-title":"Theory of Semi-Feasible Algorithms","author":"L.A. Hemaspaandra","year":"2003","unstructured":"Hemaspaandra, L.A., Torenvliet, L.: Theory of Semi-Feasible Algorithms. Springer, New York (2003)"},{"issue":"1-2","key":"40_CR25","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/0304-3975(94)00290-Y","volume":"145","author":"L.A. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L.A., Zhigen, J.: P-selectivity: Intersections and indices. Theoretical Computer Science\u00a0145(1-2), 371\u2013380 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"40_CR26","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"C. Jockusch","year":"1968","unstructured":"Jockusch, C.: Semirecursive sets and positive reducibility. Transactions of the American Mathematical Society\u00a0131(2), 420\u2013436 (1968)","journal-title":"Transactions of the American Mathematical Society"},{"key":"40_CR27","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Lipton, R.J.: Some connections between nonuniform and uniform complexity classes. In: STOC, pp. 302\u2013309 (1980)","DOI":"10.1145\/800141.804678"},{"issue":"2","key":"40_CR28","first-page":"209","volume":"26","author":"K. Ko","year":"1983","unstructured":"Ko, K.: On self-reducibility and weak P-selectivity. JCSS\u00a026(2), 209\u2013221 (1983)","journal-title":"JCSS"},{"key":"40_CR29","doi-asserted-by":"crossref","unstructured":"Lipton, R., Young, N.E.: Simple strategies for large zero-sum games with applications to complexity theory. In: Proceedings of ACM Symposium on Theory of Computing, pp. 734\u2013740 (1994)","DOI":"10.1145\/195058.195447"},{"issue":"4","key":"40_CR30","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C. Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H.: Algebraic methods for interactive proof systems. J. ACM\u00a039(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"issue":"5","key":"40_CR31","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. J. of the ACM\u00a041(5), 960\u2013981 (1994)","journal-title":"J. of the ACM"},{"key":"40_CR32","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.2140\/pjm.1963.13.1343","volume":"13","author":"J.W. Moon","year":"1963","unstructured":"Moon, J.W.: An extension of Landau\u2019s theorem on tournaments. Pacific J. Math.\u00a013, 1343\u20131345 (1963)","journal-title":"Pacific J. Math."},{"key":"40_CR33","volume-title":"Topics on tournaments","author":"J.W. Moon","year":"1968","unstructured":"Moon, J.W.: Topics on tournaments. Rinehart and Winston, New York (1968)"},{"issue":"1","key":"40_CR34","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01448847","volume":"100","author":"J. Neumann Von","year":"1928","unstructured":"Von Neumann, J.: Zur theorie der gesellschaftsspiele. Mathematische Annalen\u00a0100(1), 295\u2013320 (1928)","journal-title":"Mathematische Annalen"},{"key":"40_CR35","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1145\/509907.510015","volume-title":"STOC 2002: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing","author":"R. O\u2019Donnell","year":"2002","unstructured":"O\u2019Donnell, R.: Hardness amplification within NP. In: STOC 2002: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, pp. 751\u2013760. ACM, New York (2002)"},{"issue":"5","key":"40_CR36","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1137\/S0097539793258131","volume":"24","author":"M. Ogihara","year":"1995","unstructured":"Ogihara, M.: Polynomial-time membership comparable sets. SIAM J. Comput.\u00a024(5), 1068\u20131081 (1995)","journal-title":"SIAM J. Comput."},{"key":"40_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/3-540-09510-1_44","volume-title":"Automata, Languages, and Programming","author":"A.L. Selman","year":"1979","unstructured":"Selman, A.L.: P-Selective Sets, Tally Languages, and the Behavior of Polynomial Time Reducibilities on NP. In: Maurer, H.A. (ed.) ICALP 1979. LNCS, vol.\u00a071, pp. 546\u2013555. Springer, Heidelberg (1979)"},{"issue":"1","key":"40_CR38","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/S0019-9958(82)80084-3","volume":"52","author":"A.L. Selman","year":"1982","unstructured":"Selman, A.L.: Analogues of semicursive sets and effective reducibilities to the study of NP complexity. Information and Control\u00a052(1), 36\u201351 (1982)","journal-title":"Information and Control"},{"issue":"4","key":"40_CR39","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"Baker, T., Gill, J., Solovay, R.: Relativizations of the $ \\mathcal{P} =? \\mathcal{NP}$ question. SIAM Journal on Computing\u00a04(4), 431\u2013442 (1975)","journal-title":"SIAM Journal on Computing"},{"key":"40_CR40","unstructured":"Thakur, M.: On optimal advice for P-selective sets. Technical Report TR-819, Department of Computer Science. University of Rochester, Rochester, NY (2003)"},{"key":"40_CR41","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF02090391","volume":"24","author":"S. Toda","year":"1991","unstructured":"Toda, S.: On polynomial-time truth-table reducibility of intractable sets to P-selective sets. Theory of Computing Systems\u00a024, 69\u201382 (1991), doi:10.1007\/BF02090391","journal-title":"Theory of Computing Systems"},{"key":"40_CR42","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1109\/SFCS.2003.1238187","volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003","author":"L. Trevisan","year":"2003","unstructured":"Trevisan, L.: List-decoding using the XOR lemma. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, pp. 126\u2013135. IEEE Computer Society, Washington, DC (2003)"},{"key":"40_CR43","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1060590.1060595","volume-title":"STOC 2005: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing","author":"L. Trevisan","year":"2005","unstructured":"Trevisan, L.: On uniform amplification of hardness in NP. In: STOC 2005: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 31\u201338. ACM, New York (2005)"},{"issue":"4","key":"40_CR44","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","volume":"16","author":"L. Trevisan","year":"2007","unstructured":"Trevisan, L., Vadhan, S.P.: Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity\u00a016(4), 331\u2013364 (2007)","journal-title":"Computational Complexity"},{"key":"40_CR45","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/s00037-004-0187-1","volume":"13","author":"E. Viola","year":"2005","unstructured":"Viola, E.: The complexity of constructing pseudorandom generators from hard functions. Computational Complexity\u00a013, 147\u2013188 (2005), doi:10.1007\/s00037-004-0187-1","journal-title":"Computational Complexity"},{"issue":"2","key":"40_CR46","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(95)00073-L","volume":"55","author":"J. Wang","year":"1995","unstructured":"Wang, J.: Some results on selectivity and self-reducibility. Inf. Proc. Letters\u00a055(2), 81\u201387 (1995)","journal-title":"Inf. Proc. Letters"},{"key":"40_CR47","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some complexity questions related to distributed computing. In: Proc. of the 11th ACM Symp. on the Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32241-9_40.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T21:09:20Z","timestamp":1743973760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32241-9_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642322402","9783642322419"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32241-9_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}