{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:26:16Z","timestamp":1758273976897},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,10,29]],"date-time":"2013-10-29T00:00:00Z","timestamp":1383004800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s00037-013-0075-7","type":"journal-article","created":{"date-parts":[[2013,10,28]],"date-time":"2013-10-28T06:19:11Z","timestamp":1382941151000},"page":"1-42","source":"Crossref","is-referenced-by-count":3,"title":["Choosing, Agreeing, and Eliminating in Communication Complexity"],"prefix":"10.1007","volume":"23","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Ben Daniel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enav","family":"Weinreb","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,29]]},"reference":[{"key":"75_CR1","unstructured":"M. Agrawal & V. Arvind (1994). Polynomial time truth-table reductions to P-selective sets. In Structure in Complexity Theory Conference, 24\u201330."},{"issue":"2","key":"75_CR2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1006\/jcss.2001.1761","volume":"63","author":"A. Ambainis","year":"2001","unstructured":"Ambainis A., Buhrman H, Gasarch W, Kalyanasundaramd B., Torenvliete L. (2001) The communication complexity of enumeration, elimination, and selection. Journal of Computer and System Sciences 63(2): 148\u2013185","journal-title":"Journal of Computer and System Sciences"},{"key":"75_CR3","unstructured":"A. Amihood, R. Beigel & W. I. Gasarch (2000). Some connections between bounded query classes and non-uniform complexity. Technical Report 024, Electronic Colloquium on Computational Complexity."},{"key":"75_CR4","doi-asserted-by":"crossref","unstructured":"Z. Bar-Yossef, T. S. Jayram, R Kumar & D. Sivakumar (2002). An information statistics approach to data stream and communication complexity. In Proceedings of the 43nd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, 209\u2013218.","DOI":"10.1109\/SFCS.2002.1181944"},{"key":"75_CR5","doi-asserted-by":"crossref","unstructured":"B. Barak, M. Braverman, X. Chen & A. Rao (2010). How to compress interactive communication. In Proceedings of the Fourty-second Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 67\u201376.","DOI":"10.1145\/1806689.1806701"},{"key":"75_CR6","doi-asserted-by":"crossref","unstructured":"P. Beame, T. Pitassi, N. Segerlind & A. Wigderson (2005). A direct sum theorem for corruption and the multiparty nof communication complexity of set disjointness. In the Proceedings of the 20th Annual IEEE Conference on Computational Complexity, 52\u201366.","DOI":"10.1109\/CCC.2005.1"},{"issue":"1","key":"75_CR7","doi-asserted-by":"crossref","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 (1993) Terse, superterse, and verbose sets. Inf. Comput. 103(1): 68\u201385","journal-title":"Inf. Comput."},{"issue":"1","key":"75_CR8","doi-asserted-by":"crossref","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., (2000) The complexity of $${{\\rm Odd}^{A}_{n}}$$ Odd n A . Journal of Symbolic Logic 65(1): 1ndash;18","journal-title":"Journal of Symbolic Logic"},{"key":"75_CR9","unstructured":"R. Beigel & T. Hirst (1998). One help-bit doesn\u2019t help. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, DallasTX, 124\u2013130."},{"key":"75_CR10","first-page":"12","volume":"120","author":"R. Beigel","year":"1994","unstructured":"Beigel R., Kummer M., Stephan F. (1994) Approximable sets. Information and Computation 120: 12\u201323","journal-title":"Information and Computation"},{"issue":"1","key":"75_CR11","first-page":"34","volume":"82","author":"J. Cai","year":"1989","unstructured":"Cai J., Hemachandra L.A. (1989) Enumerative counting is hard. Information and Control 82(1): 34\u201344","journal-title":"Information and Control"},{"key":"75_CR12","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti, Y. Shi, A. Wirth & A. Yao (2001). Informational complexity and the direct sum problem for simultaneous message complexity. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, Las Vegas NV, 270\u2013278.","DOI":"10.1109\/SFCS.2001.959901"},{"key":"75_CR13","doi-asserted-by":"crossref","unstructured":"J. Edmonds, R. Impagliazzo, S. Rudich & J. Sgall (1991). Communication complexity towards lower bounds on circuit depth. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, San Juan PR, 249\u2013257.","DOI":"10.1109\/SFCS.1991.185375"},{"issue":"4","key":"75_CR14","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1137\/S0097539792235864","volume":"24","author":"T. Feder","year":"1995","unstructured":"Feder T., Kushilevitz E., Naor M., Nisan N. (1995) Amortized communication complexity. SIAM Journal on Computing 24(4): 736\u2013750","journal-title":"SIAM Journal on Computing"},{"key":"75_CR15","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0304-3975(81)90074-8","volume":"16","author":"G. Galbiati","year":"1981","unstructured":"Galbiati G., Fischer M.J. (1981) On the complexity of 2-output Boolean networks. Theoretical Computer Science 16: 177\u2013185","journal-title":"Theoretical Computer Science"},{"key":"75_CR16","volume-title":"Bounded Queries in Recursion Theory","author":"W. Gasarch","year":"1998","unstructured":"Gasarch W., Martin G. (1998) Bounded Queries in Recursion Theory. Birkh\u00e4user Verlag, Boston"},{"key":"75_CR17","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. (2003) Theory of Semi-Feasible Algorithms. Springer-Verlag, New York"},{"key":"75_CR18","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, R. Raz & A. Wigderson (1994). A direct product theorem. In Structure in Complexity Theory Conference, 88\u201396.","DOI":"10.1109\/SCT.1994.315814"},{"key":"75_CR19","unstructured":"R. Jain, H. Klauck & M. Santha (2010). Optimal direct sum results for deterministic and randomized decision tree complexity. Technical Report 1004.0105v1, arxiv.org. http:\/\/arxiv.org\/abs\/1004.0105v1 ."},{"key":"75_CR20","doi-asserted-by":"crossref","unstructured":"R. Jain, J. Radhakrishnan & P. Sen (2003). A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming ICALP 2003, Eindhoven, The Netherlands, 300\u2013315.","DOI":"10.1007\/3-540-45061-0_26"},{"issue":"2","key":"75_CR21","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. (1968) Semirecursive sets and positive reducibility. Transactions of the American Mathematical Society 131(2): 420\u2013436","journal-title":"Transactions of the American Mathematical Society"},{"issue":"4","key":"75_CR22","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram B., Schnitger G. (1992) The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics 5(4): 545\u2013557","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"75_CR23","doi-asserted-by":"crossref","unstructured":"M. Karchmer, E. Kushilevitz & N. Nisan, (1995a). Fractional covers and communication complexity. SIAM Journal on Discrete Mathematics 8(1), 76\u201392.","DOI":"10.1137\/S0895480192238482"},{"key":"75_CR24","doi-asserted-by":"crossref","unstructured":"M. Karchmer, R. Raz & A. Wigderson (1995B). Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity 5(3\/4), 191\u2013204.","DOI":"10.1007\/BF01206317"},{"issue":"2","key":"75_CR25","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1137\/0403021","volume":"3","author":"M. Karchmer","year":"1990","unstructured":"Karchmer M., Wigderson A. (1990) Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics 3(2), 255\u2013265","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"75_CR26","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(83)90013-2","volume":"26","author":"K. Ko","year":"1983","unstructured":"Ko K. (1983) On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences 26(2): 209\u2013221","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"75_CR27","doi-asserted-by":"crossref","first-page":"677","DOI":"10.2307\/2275299","volume":"57","author":"M. Kummer","year":"1992","unstructured":"Kummer M. (1992) A proof of Beigel\u2019s cardinality conjecture. Journal of Symbolic Logic 57(2): 677\u2013681","journal-title":"Journal of Symbolic Logic"},{"key":"75_CR28","unstructured":"E. Kushilevitz & N. Nisan (1997). Communication Complexity. Cambridge University Press."},{"issue":"2","key":"75_CR29","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman I. (1991) Private vs. common random bits in communication complexity. Inf. Process. Lett. 39(2): 67\u201371","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"75_CR30","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1137\/S0097539795282444","volume":"28","author":"N. Nisan","year":"1999","unstructured":"Nisan N., Rudich S., Saks M. (1999) Products and help bits in decision trees. SIAM Journal on Computing 28(3): 1035\u20131050","journal-title":"SIAM Journal on Computing"},{"key":"75_CR31","doi-asserted-by":"crossref","unstructured":"I. Parnafes, R. Raz & A. Wigderson (1997). Direct product results and the GCD problem, in old and new communication models. In Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, El Paso TX, 363\u2013372.","DOI":"10.1145\/258533.258620"},{"key":"75_CR32","unstructured":"W.J. Paul (1974). Realizing Boolean functions on disjoint sets of variables. Technical report, Cornell University, Ithaca, NY, USA."},{"key":"75_CR33","doi-asserted-by":"crossref","unstructured":"A. A. Razborov (1990). On the distributional complexity of disjointness. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming ICALP 1990, Warwick, UK, 249\u2013253. Springer.","DOI":"10.1007\/BFb0032036"},{"key":"75_CR34","doi-asserted-by":"crossref","unstructured":"A. L. Selman (1979). P-selective sets, tally languages, and the behavior of polynomial time reducibilities on NP. In Proceedings of the 6th International Colloquium on Automata, Languages and Programming ICALP 1979, London, UK, 546\u2013555. Springer-Verlag. ISBN 3-540-09510-1.","DOI":"10.1007\/3-540-09510-1_44"},{"key":"75_CR35","doi-asserted-by":"crossref","unstructured":"A. L. Selman (1982a). Analogues of Semicursive Sets and Effective Reducibilities to the Study of NP Complexity. Information and Control 52(1), 36\u201351.","DOI":"10.1016\/S0019-9958(82)80084-3"},{"key":"75_CR36","doi-asserted-by":"crossref","unstructured":"A. L. Selman (1982B). Reductions on NP and P-Selective Sets. Theor. Comput. Sci. 19, 287\u2013304.","DOI":"10.1016\/0304-3975(82)90039-1"},{"key":"75_CR37","unstructured":"R. Shaltiel (2001). Towards proving strong direct product theorems. In Proceedings of the 16th IEEE Conference on Computational Complexity, Chicago IL, 107\u2013119."},{"issue":"2","key":"75_CR38","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1006\/jcss.1999.1653","volume":"59","author":"D. Sivakumar","year":"1999","unstructured":"Sivakumar D. (1999) On membership comparable sets. Journal of Computer and System Sciences 59(2): 270\u2013280","journal-title":"Journal of Computer and System Sciences"},{"key":"75_CR39","first-page":"937","volume":"15","author":"D. Uhlig","year":"1974","unstructured":"Uhlig D. (1974) On the synthesis of self-correcting schemes from functional elements with a small number of reliable elements. Mat. Zametki 15: 937\u2013944","journal-title":"Mat. Zametki"},{"key":"75_CR40","doi-asserted-by":"crossref","unstructured":"A. C. Yao (1979). Some complexity questions related to distributed computing. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, Atlanta GA, 209\u2013213.","DOI":"10.1145\/800135.804414"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0075-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-013-0075-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-013-0075-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T07:09:30Z","timestamp":1564556970000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-013-0075-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,29]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["75"],"URL":"https:\/\/doi.org\/10.1007\/s00037-013-0075-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,29]]}}}