{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:41Z","timestamp":1725511781258},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_43","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"500-511","source":"Crossref","is-referenced-by-count":5,"title":["Languages with Bounded Multiparty Communication Complexity"],"prefix":"10.1007","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Krebs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Tesson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Denis","family":"Th\u00e9rien","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"43_CR1","doi-asserted-by":"crossref","unstructured":"Ambainis, A.: Upper bounds on multiparty communication complexity of shifts. In: Proc. 13th STACS, pp. 631\u2013642 (1996)","DOI":"10.1007\/3-540-60922-9_51"},{"issue":"2","key":"43_CR2","first-page":"204","volume":"45","author":"L. Babai","year":"1992","unstructured":"Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. JCSS\u00a045(2), 204\u2013232 (1992)","journal-title":"JCSS"},{"issue":"2","key":"43_CR3","first-page":"101","volume":"70","author":"D.A.M. Barrington","year":"2005","unstructured":"Barrington, D.A.M., et al.: First order expressibility of languages with neutral letters or: The Crane Beach conjecture. JCSS\u00a070(2), 101\u2013127 (2005)","journal-title":"JCSS"},{"issue":"3","key":"43_CR4","first-page":"374","volume":"50","author":"D.A.M. Barrington","year":"1995","unstructured":"Barrington, D.A.M., Straubing, H.: Superlinear lower bounds for bounded-width branching programs. JCSS\u00a050(3), 374\u2013381 (1995)","journal-title":"JCSS"},{"key":"43_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1176","DOI":"10.1007\/11523468_95","volume-title":"Automata, Languages and Programming","author":"P. Beame","year":"2005","unstructured":"Beame, P., Pitassi, T., Segerlind, N.: Lower bounds for Lov\u00e1sz-Schrijver systems and beyond follow from multiparty communication complexity. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1176\u20131188. Springer, Heidelberg (2005)"},{"key":"43_CR6","doi-asserted-by":"crossref","unstructured":"Beame, P., Vee, E.: Time-space tradeoffs multiparty communication complexity and nearest neighbor problems. In: 34th STOC, pp. 688\u2013697 (2002)","DOI":"10.1145\/510002.510006"},{"key":"43_CR7","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Furst, M.L., Lipton, R.J.: Multi-party protocols. In: STOC\u201983, pp. 94\u201399 (1983)","DOI":"10.1145\/800061.808737"},{"key":"43_CR8","unstructured":"Chattopadhyay, A., et al.: Languages with bounded multiparty communication complexity. In: ECCC, TR06-118 (2006)"},{"issue":"5","key":"43_CR9","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1137\/S0097539795285631","volume":"27","author":"M. Goldmann","year":"1998","unstructured":"Goldmann, M., H\u00e5stad, J.: Monotone circuits for connectivity have depth (log n)2\u2009\u2212\u2009o(1). SIAM J. Comput.\u00a027(5), 1283\u20131294 (1998)","journal-title":"SIAM J. Comput."},{"key":"43_CR10","series-title":"Series in Discrete Mathematics","volume-title":"Ramsey Theorey","author":"R.L. Graham","year":"1980","unstructured":"Graham, R.L., Rotschild, B.L., Spencer, J.H.: Ramsey Theorey. Series in Discrete Mathematics. Wiley Interscience, Chichester (1980)"},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"Grolmusz, V.: Separating the communication complexities of MOD m and MOD p circuits. In: Proc. 33rd FOCS, pp. 278\u2013287 (1992)","DOI":"10.1109\/SFCS.1992.267764"},{"issue":"1","key":"43_CR12","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1006\/inco.1994.1051","volume":"112","author":"V. Grolmusz","year":"1994","unstructured":"Grolmusz, V.: The BNS lower bound for multi-party protocols in nearly optimal. Information and Computation\u00a0112(1), 51\u201354 (1994)","journal-title":"Information and Computation"},{"key":"43_CR13","volume-title":"Communication Complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"43_CR14","unstructured":"Nisan, N.: The communication complexity of treshold gates. In: Combinatorics, Paul Erd\u00f6s is Eighty, vol.\u00a01, pp. 301\u2013315 (1993)"},{"key":"43_CR15","first-page":"679","volume-title":"Handbook of language theory, vol. 1","author":"J.-E. Pin","year":"1997","unstructured":"Pin, J.-E.: Syntactic semigroups. In: Handbook of language theory, vol. 1, pp. 679\u2013746. Springer, Heidelberg (1997)"},{"issue":"5\u20136","key":"43_CR16","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1017\/S0963548303005790","volume":"12","author":"P. Pudl\u00e1k","year":"2003","unstructured":"Pudl\u00e1k, P.: An application of Hindman\u2019s theorem to a problem on communication complexity. Combinatorics, Probability and Computing\u00a012(5\u20136), 661\u2013670 (2003)","journal-title":"Combinatorics, Probability and Computing"},{"key":"43_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BFb0055038","volume-title":"Automata, Languages and Programming","author":"J.-F. Raymond","year":"1998","unstructured":"Raymond, J.-F., Tesson, P., Th\u00e9rien, D.: An algebraic approach to communication complexity. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 29\u201340. Springer, Heidelberg (1998)"},{"issue":"2","key":"43_CR18","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/PL00001602","volume":"9","author":"R. Raz","year":"2000","unstructured":"Raz, R.: The BNS-Chung criterion for multi-party communication complexity. Computational Complexity\u00a09(2), 113\u2013122 (2000)","journal-title":"Computational Complexity"},{"issue":"3","key":"43_CR19","first-page":"405","volume":"47","author":"M. Szegedy","year":"1993","unstructured":"Szegedy, M.: Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC. JCSS\u00a047(3), 405\u2013423 (1993)","journal-title":"JCSS"},{"issue":"2","key":"43_CR20","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s00224-004-1190-2","volume":"38","author":"P. Tesson","year":"2005","unstructured":"Tesson, P., Th\u00e9rien, D.: Complete classifications for the communication complexity of regular languages. Theory of Computing Systems\u00a038(2), 135\u2013159 (2005)","journal-title":"Theory of Computing Systems"},{"key":"43_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1007\/11523468_43","volume-title":"Automata, Languages and Programming","author":"P. Tesson","year":"2005","unstructured":"Tesson, P., Th\u00e9rien, D.: Restricted two-variable sentences, circuits and communication complexity. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 526\u2013538. Springer, Heidelberg (2005)"},{"key":"43_CR22","first-page":"195","volume-title":"Combinatorics on Words: Progress and Perspectives","author":"D. Th\u00e9rien","year":"1983","unstructured":"Th\u00e9rien, D.: Subword counting and nilpotent groups. In: Combinatorics on Words: Progress and Perspectives, pp. 195\u2013208. Academic Press, London (1983)"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T05:11:56Z","timestamp":1605762716000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_43","relation":{},"subject":[]}}