{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T17:10:23Z","timestamp":1740244223689,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_39","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"451-462","source":"Crossref","is-referenced-by-count":1,"title":["Choosing, Agreeing, and Eliminating in Communication Complexity"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Sebastian","family":"Ben Daniel","sequence":"additional","affiliation":[]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]},{"given":"Enav","family":"Weinreb","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Arvind, V.: Polynomial time truth-table reductions to P-selective sets. In: Structure in Complexity Theory Conference, pp. 24\u201330 (1994)","DOI":"10.1109\/SCT.1994.315821"},{"issue":"2","key":"39_CR2","first-page":"148","volume":"63","author":"A. Ambainis","year":"2001","unstructured":"Ambainis, A., Buhrman, H., Gasarch, W., Kalyanasundaramd, B., Torenvliete, L.: The communication complexity of enumeration, elimination, and selection. JCSS\u00a063(2), 148\u2013185 (2001)","journal-title":"JCSS"},{"key":"39_CR3","unstructured":"Amihood, A., Beigel, R., Gasarch, W.I.: Some connections between bounded query classes and non-uniform complexity. ECCC\u00a07(024) (2000)"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D.: An information statistics approach to data stream and communication complexity. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, pp. 209\u2013218 (2002)","DOI":"10.1109\/SFCS.2002.1181944"},{"issue":"1","key":"39_CR5","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1006\/inco.1993.1014","volume":"103","author":"R. Beigel","year":"1993","unstructured":"Beigel, R., Gasarch, W.I., Gill, J., Owings, J.C.: Terse, superterse, and verbose sets. Inf. Comput.\u00a0103(1), 68\u201385 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"39_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2586523","volume":"65","author":"R. Beigel","year":"2000","unstructured":"Beigel, R., Gasarch, W.I., Kummer, M., Martin, G., McNicholl, T., Stephan, F.: The complexity of Odd $^{A}_{\\mbox{n}}$ . J. Symb. Log.\u00a065(1), 1\u201318 (2000)","journal-title":"J. Symb. Log."},{"key":"39_CR7","doi-asserted-by":"crossref","unstructured":"Beigel, R., Hirst, T.: One help-bit doesn\u2019t help. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 124\u2013130 (1998)","DOI":"10.1145\/276698.276720"},{"key":"39_CR8","first-page":"12","volume":"120","author":"R. Beigel","year":"1994","unstructured":"Beigel, R., Kummer, M., Stephan, F.: Approximable sets. Information and Computation\u00a0120, 12\u201323 (1994)","journal-title":"Information and Computation"},{"issue":"1","key":"39_CR9","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/0890-5401(89)90063-1","volume":"82","author":"J. Cai","year":"1989","unstructured":"Cai, J., Hemachandra, L.A.: Enumerative counting is hard. Inf. Comput.\u00a082(1), 34\u201344 (1989)","journal-title":"Inf. Comput."},{"issue":"4","key":"39_CR10","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1137\/S0097539792235864","volume":"24","author":"T. Feder","year":"1995","unstructured":"Feder, T., Kushilevitz, E., Naor, M., Nisan, N.: Amortized communication complexity. SIAM Journal on Computing\u00a024(4), 736\u2013750 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"39_CR11","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0304-3975(81)90074-8","volume":"16","author":"G. Galbiati","year":"1981","unstructured":"Galbiati, G., Fischer, M.J.: On the complexity of 2-output Boolean networks. Theor. Comput. Sci.\u00a016, 177\u2013185 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Gasarch, W., Martin, G.: Bounded queries in recursion theory (1998)","DOI":"10.1007\/978-1-4612-0635-4"},{"key":"39_CR13","doi-asserted-by":"crossref","unstructured":"Hemaspaandra, L.A., Torenvliet, L.: Theory of Semi-Feasible Algorithms (2003)","DOI":"10.1007\/978-3-662-05080-4"},{"key":"39_CR14","unstructured":"Jain, R., Klauck, H., Santha, M.: Optimal direct sum results for deterministic and randomized decision tree complexity. Technical Report 1004.0105v1, arxiv.org (2010), http:\/\/arxiv.org\/abs\/1004.0105v1"},{"issue":"2","key":"39_CR15","doi-asserted-by":"crossref","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"},{"issue":"1","key":"39_CR16","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1137\/S0895480192238482","volume":"8","author":"M. Karchmer","year":"1995","unstructured":"Karchmer, M., Kushilevitz, E., Nisan, N.: Fractional covers and communication complexity. SIAM J. on Discrete Mathematics\u00a08(1), 76\u201392 (1995)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"39_CR17","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: On proving superlogarithmic depth lower bounds via the direct sum in communication complexity. In: 6th IEEE Structure in Complexity Theory, pp. 299\u2013304 (1991)","DOI":"10.1109\/SCT.1991.160273"},{"issue":"2","key":"39_CR18","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require superlogarithmic depth. SIAM J. on Discrete Mathematics\u00a03(2), 255\u2013265 (1990)","journal-title":"SIAM J. on Discrete Mathematics"},{"issue":"2","key":"39_CR19","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"},{"issue":"2","key":"39_CR20","doi-asserted-by":"publisher","first-page":"677","DOI":"10.2307\/2275299","volume":"57","author":"M. Kummer","year":"1992","unstructured":"Kummer, M.: A proof of Beigel\u2019s cardinality conjecture. J. Symb. Log.\u00a057(2), 677\u2013681 (1992)","journal-title":"J. Symb. Log."},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity (1997)","DOI":"10.1017\/CBO9780511574948"},{"issue":"3","key":"39_CR22","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1137\/S0097539795282444","volume":"28","author":"N. Nisan","year":"1999","unstructured":"Nisan, N., Rudich, S., Saks, M.: Products and help bits in decision trees. SIAM J. Comput.\u00a028(3), 1035\u20131050 (1999)","journal-title":"SIAM J. Comput."},{"key":"39_CR23","unstructured":"Paul, W.J.: Realizing Boolean functions on disjoint sets of variables. Technical report, Cornell University, Ithaca, NY, USA (1974)"},{"key":"39_CR24","first-page":"546","volume-title":"6th ICALP","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: 6th ICALP, pp. 546\u2013555. Springer, Heidelberg (1979)"},{"issue":"1","key":"39_CR25","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"},{"key":"39_CR26","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(82)90039-1","volume":"19","author":"A.L. Selman","year":"1982","unstructured":"Selman, A.L.: Reductions on NP and P-selective sets. Theor. Comput. Sci.\u00a019, 287\u2013304 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"39_CR27","doi-asserted-by":"crossref","unstructured":"Shaltiel, R.: Towards proving strong direct product theorems. In: Proc. of the 16th IEEE Conf. on Computational Complexity, pp. 107\u2013119 (2001)","DOI":"10.1109\/CCC.2001.933878"},{"issue":"2","key":"39_CR28","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/jcss.1999.1653","volume":"59","author":"D. Sivakumar","year":"1999","unstructured":"Sivakumar, D.: On membership comparable sets. J. Comput. Syst. Sci.\u00a059(2), 270\u2013280 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"39_CR29","first-page":"937","volume":"15","author":"D. Uhlig","year":"1974","unstructured":"Uhlig, D.: On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Mat. Zametki\u00a015, 937\u2013944 (1974)","journal-title":"Mat. Zametki"},{"key":"39_CR30","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","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:29Z","timestamp":1740241889000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}