{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:03Z","timestamp":1750694763396,"version":"3.41.0"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T00:00:00Z","timestamp":1595203200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1412958 and CCF-1657377"],"award-info":[{"award-number":["CCF-1412958 and CCF-1657377"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>\n            Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set\n            <jats:italic>x<\/jats:italic>\n            \u2286 [\n            <jats:italic>n<\/jats:italic>\n            ] and Bob ends up with a set\n            <jats:italic>y<\/jats:italic>\n            \u2286 [\n            <jats:italic>n<\/jats:italic>\n            ], such that (\n            <jats:italic>x<\/jats:italic>\n            ,\n            <jats:italic>y<\/jats:italic>\n            ) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant \u03b2 &lt; 1, this requires \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            ) communication even to get within statistical distance 1\u2212 \u03b2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that \u03a9 (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) communication is required to get within some constant statistical distance \u025b &gt; 0 of the uniform distribution over all pairs of disjoint sets of size \u221a\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3404858","type":"journal-article","created":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T16:05:26Z","timestamp":1595261126000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Lower Bound for Sampling Disjoint Sets"],"prefix":"10.1145","volume":"12","author":[{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[{"name":"Stanford, California, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[{"name":"University of Memphis, Tennessee, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-013-9527-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a004"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490272"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.12"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188862"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979935476"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316361"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.12"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0220-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.82"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.45"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.17"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276748"},{"volume-title":"Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM\u201915)","year":"2015","author":"Bottesch Ralph","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.77"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061400"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488628"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767425"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.22"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611501"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2013.006"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214414"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3235586.3235600"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2018.v014a006"},{"volume-title":"Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM\u201912)","author":"Dasgupta Anirban","key":"e_1_2_1_31_1"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2141938.2141941"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62389-4_17"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a010"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/080722771"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M103145X"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0104-9"},{"key":"e_1_2_1_39_1","first-page":"1","article-title":"Communication complexity of set-disjointness for all probabilities","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","journal-title":"Theory Comput."},{"volume-title":"Proceedings of the 23rd International Conference on Randomization and Computation (RANDOM\u201919)","year":"2019","author":"G\u00f6\u00f6s Mika","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","first-page":"51","article-title":"The BNS lower bound for multi-party protocols is nearly optimal. Info","volume":"112","author":"Grolmusz Vince","year":"1994","journal-title":"Comput."},{"volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909)","year":"2009","author":"Gronemeier Andr\u00e9","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a011"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/646516.696149"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.105"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374462"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238196"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2258372"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_42"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214415"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806702"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896888"},{"volume-title":"Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201914)","year":"2014","author":"Klauck Hartmut","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063235X"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0176-4"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.15"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0276-2"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90035-U"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0039-3"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/09075336X"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833232"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_1_66_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya","volume":"67","author":"Razborov Alexander","year":"2003","journal-title":"Math."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.78"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842661"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629334"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/120891587"},{"key":"e_1_2_1_73_1","first-page":"5","article-title":"Quantum communication complexity of block-composed functions","volume":"9","author":"Shi Yaoyun","year":"2009","journal-title":"Quant. Info. Comput."},{"key":"e_1_2_1_74_1","unstructured":"Pascal Tesson. 2003. Computational Complexity Questions Related to Finite Monoids and Semigroups. Ph.D. Dissertation. McGill University.  Pascal Tesson. 2003. Computational Complexity Questions Related to Finite Monoids and Semigroups. Ph.D. Dissertation. McGill University."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/100814998"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_56"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085983X"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/2934308"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1198405"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/120898553"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2016.002"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.5555\/3235586.3235595"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_88"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3404858","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3404858","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:44Z","timestamp":1750191464000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3404858"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,20]]},"references-count":80,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3404858"],"URL":"https:\/\/doi.org\/10.1145\/3404858","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,7,20]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}