{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T02:14:02Z","timestamp":1791080042840,"version":"4.1.0"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1992,11]]},"abstract":"<jats:p>It is shown that, for inputs of length n, the probabilistic (bounded error) communication complexity of set intersection is $\\Theta ( n )$. Since set intersection can be recognized nondeterministically by exchanging $O( \\log n )$ bits, the result implies an exponential gap between nondeterminism and probabilism. This gap is the largest possible. The first general technique to analyze the probabilistic communication complexity of sparse languages is also described.<\/jats:p>","DOI":"10.1137\/0405044","type":"journal-article","created":{"date-parts":[[2005,2,23]],"date-time":"2005-02-23T08:04:07Z","timestamp":1109145847000},"page":"545-557","source":"Crossref","is-referenced-by-count":255,"title":["The Probabilistic Communication Complexity of Set Intersection"],"prefix":"10.1137","volume":"5","author":[{"given":"Bala","family":"Kalyanasundaram","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Schintger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,8]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.22"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"A. V. Aho, J. D. Ullman, M. Yannakakis, On notions of information transfer in VLSI circuits, Proc. 14th Annual ACM Symposium on Theory of Computing, Boston, MA, 1983, 133\u2013139","DOI":"10.1145\/800061.808742"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"L. Babai, P. Frankl, J. Simon, BPP and the Polynomial Time Hierarchy in Communication Complexity Theory, Proc. 27th Annual Symposium on Foundations of Computer Science, Toronto, Ontario, Canada, 1986, 337\u2013347","DOI":"10.1109\/SFCS.1986.15"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, Unbiased bits from weak sources of randomness, Proc. 26th Annual Symposium on Foundations of Computer Science, Portland, OR, 1985, 429\u2013442","DOI":"10.1109\/SFCS.1985.62"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"P. Duris, Z. Galil, G. Schnitger, Lower bounds on communication complexity, Proc. 16th Annual ACM Symposium on Theory of Computing, Washington, DC, 1984, 81\u201391","DOI":"10.1145\/800057.808668"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"B. Halstenberg, R. Reischuk, On different modes of communication, Proc. 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, 1988, 162\u2013172","DOI":"10.1145\/62212.62226"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/0213052"},{"key":"R9","first-page":"1","volume":"1","author":"Kolmogorov A. N.","year":"1965","journal-title":"Problems Inform. Transmission"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram, G. Schnitger, The probabilistic communication complexity of set intersection, Proc. 2nd Annual Structure in Complexity Theory Conference, Ithaca, NY, 1987, 41\u201349","DOI":"10.1109\/PSCT.1987.10319253"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn, E. M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing, Proc. 14th Annual ACM Symposium on Theory of Computing, San Francisco, CA, 1982, 330\u2013337","DOI":"10.1145\/800070.802208"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou, M. Sipser, Communication complexity, Proc. 14th Annual ACM Symposium on Theory of Computing, San Francisco, CA, 1982, 196\u2013200","DOI":"10.1145\/800070.802192"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"R. Raz, A. Wigderson, Monotone circuits for matching require linear depth, Proc. 22nd Annual ACM Symposium on Theory of Computing, Baltimore, MD, 1990, 287\u2013292","DOI":"10.1145\/100216.100253"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032036"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Lower bounds by probabilistic arguments, Proc. 24th Annual Symposium on Foundations of Computer Science, Tucson, AZ, 1983, 420\u2013428","DOI":"10.1109\/SFCS.1983.30"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Some Complexity Questions Related to Distributed Computing, Proc. 11th Annual ACM Symposium on Theory of Computing, Atlanta, GA, 1979, 209\u2013213","DOI":"10.1145\/800135.804414"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0405044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:53:41Z","timestamp":1787316821000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0405044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,11]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1992,11]]}},"alternative-id":["10.1137\/0405044"],"URL":"https:\/\/doi.org\/10.1137\/0405044","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,11]]}}}