{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:13:15Z","timestamp":1725455595562},"publisher-location":"Berlin\/Heidelberg","reference-count":13,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540552367"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022447","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:03:27Z","timestamp":1131861807000},"page":"193-199","source":"Crossref","is-referenced-by-count":0,"title":["The communication complexity of the two list problem"],"prefix":"10.1007","author":[{"given":"Alon","family":"Itai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"\u201cA fast and simple randomized parallel algorithm for the maximal independent set problem\u201d. Alon, N., L. Babai, A. Itai, J. Algorithms, 7, 567\u2013583, (1986).","journal-title":"J. Algorithms"},{"key":"14_CR2","unstructured":"Alon, N., O. Goldreich, J. Hastead and R. Peralta, \u201cSimple construction of almost k-wise independent random variables\u201d. FOCS 90."},{"key":"14_CR3","first-page":"143","volume":"18","author":"J. L. Carter","year":"1979","unstructured":"Carter, J. L., and M. N. Wegman, \u201cUniversal classes of hash functions,\u201d JCSS 18, 143\u2013154 (1979).","journal-title":"JCSS"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Duris, P., and Z. Galil. \u201cTwo lower bounds in asynchronous distributed computation,\u201d 28 FOCS, 326\u2013330, (1987).","DOI":"10.1109\/SFCS.1987.60"},{"key":"14_CR5","unstructured":"Fleischer, R., H. Jung, and K. Melhorn, \u201cA time-randomness tradeoff for communication complexity\u201d, WDAG 4, Otranto, Italy, (1990). Lecture Notes in Computer Science 486, J. van Leewen and N. Santoro, (eds.), Springer-Verlag."},{"key":"14_CR6","doi-asserted-by":"crossref","unstructured":"F\u00fcrer, M., \u201cThe power of randomness for communication complexity,\u201d STOC 1987, 178\u2013181.","DOI":"10.1145\/28395.28415"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Melhorn, K., and E.M. Schmidt, \u201cLas Vegas is better than determinism in VLSI and distributed computing,\u201d STOC 1982, 330\u2013337.","DOI":"10.1145\/800070.802208"},{"key":"14_CR8","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M., \u201cA simple parallel algorithm for the maximal independent set problem\u201d, SIAM J. Computing, 15 (1986), 1036\u20131053.","journal-title":"SIAM J. Computing"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Melhorn, K., Data structures and Algorithms 1: Sorting and Searching EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1984.","DOI":"10.1007\/978-3-642-69672-5"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Naor, J., and M. Naor, \u201cSmall-bias probability spaces: Efficient construction and applications\u201d, 22nd ACM Symposium on the Theory of Computing, 213\u2013223, (1990).","DOI":"10.1145\/100216.100244"},{"key":"14_CR11","unstructured":"Newman, I., \u201cCommunication complexity in the private random bits model is no harder than in the common bits model,\u201d unpublished manuscript, 1990."},{"key":"14_CR12","unstructured":"O'Reilly, U-M., and N. Santoro, \u201cThe expressiveness of silence\u201d, unpublished communication, (1991)."},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C. H., and M. Sipser, \u201cCommunication complexity\u201d, Fourteenth ACM Symposium on the Theory of Computing, 196\u2013200, (1982).","DOI":"10.1145\/800070.802192"}],"container-title":["Lecture Notes in Computer Science","Distributed Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022447.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:48:30Z","timestamp":1607550510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022447"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540552367"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0022447","relation":{},"subject":[]}}