{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,31]],"date-time":"2025-05-31T04:11:50Z","timestamp":1748664710759,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662486528"},{"type":"electronic","value":"9783662486535"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48653-5_31","type":"book-chapter","created":{"date-parts":[[2015,10,2]],"date-time":"2015-10-02T22:46:01Z","timestamp":1443825961000},"page":"467-479","source":"Crossref","is-referenced-by-count":1,"title":["Compressing Communication in Distributed Protocols"],"prefix":"10.1007","author":[{"given":"Yael Tauman","family":"Kalai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,5]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Linial, N.: Collective coin flipping, robust voting schemes and minima of banzhaf values. In: 26th Annual Symposium on Foundations of Computer Science, FOCS, pp. 408\u2013416 (1985)","DOI":"10.1109\/SFCS.1985.15"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Feige, U.: Noncryptographic selection protocols. In: 40th Annual Symposium on Foundations of Computer Science, FOCS, pp. 142\u2013153 (1999)","DOI":"10.1109\/SFFCS.1999.814586"},{"issue":"1","key":"31_CR3","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s00037-009-0282-4","volume":"19","author":"O Goldreich","year":"2010","unstructured":"Goldreich, O., Sheffet, O.: On the randomness complexity of property testing. Computational Complexity 19(1), 99\u2013133 (2010)","journal-title":"Computational Complexity"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1007\/978-3-662-47666-6_53","volume-title":"Automata, Languages, and Programming","author":"S Goldwasser","year":"2015","unstructured":"Goldwasser, S., Kalai, Y.T., Park, S.: Adaptively secure coin-flipping, revisited. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 663\u2013674. Springer, Heidelberg (2015)"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Komargodski, I.: Compressing communication in distributed protocols. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 22, p. 92 (2015)","DOI":"10.1007\/978-3-662-48653-5_31"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is NOT needed: SINGLE database, computationally-private information retrieval. In: 38th Annual Symposium on Foundations of Computer Science, FOCS, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"issue":"3","key":"31_CR8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF02125896","volume":"9","author":"D Lichtenstein","year":"1989","unstructured":"Lichtenstein, D., Linial, N., Saks, M.E.: Some extremal problems arising form discrete control processes. Combinatorica 9(3), 269\u2013287 (1989)","journal-title":"Combinatorica"},{"key":"31_CR9","doi-asserted-by":"crossref","unstructured":"Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: 33rd Annual ACM Symposium on Theory of Computing, STOC, pp. 590\u2013599 (2001)","DOI":"10.1145\/380752.380855"},{"issue":"2","key":"31_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Inf. Process. Lett. 39(2), 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"5","key":"31_CR12","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"31_CR13","doi-asserted-by":"publisher","first-page":"1645","DOI":"10.1137\/S0097539700376007","volume":"31","author":"A Russell","year":"2002","unstructured":"Russell, A., Saks, M.E., Zuckerman, D.: Lower bounds for leader election and collective coin-flipping in the perfect information model. SIAM J. Comput. 31(6), 1645\u20131662 (2002)","journal-title":"SIAM J. Comput."},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/j.tcs.2014.04.003","volume":"561","author":"AD Sarma","year":"2015","unstructured":"Sarma, A.D., Molla, A.R., Pandurangan, G., Upfal, E.: Fast distributed pagerank computation. Theor. Comput. Sci. 561, 113\u2013121 (2015)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48653-5_31","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T22:19:30Z","timestamp":1748643570000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48653-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662486528","9783662486535"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48653-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}