{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:20:02Z","timestamp":1764350402457,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,24]],"date-time":"2018-01-24T00:00:00Z","timestamp":1516752000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1657377"],"award-info":[{"award-number":["CCF-1657377"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            We show that\n            <jats:italic>randomized<\/jats:italic>\n            communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal\n            <jats:italic>randomized<\/jats:italic>\n            lower bounds for the Clique versus Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\u00f6\u00f6s, Pitassi, and Watson, FOCS\u201915). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.\n          <\/jats:p>","DOI":"10.1145\/3170711","type":"journal-article","created":{"date-parts":[[2018,1,26]],"date-time":"2018-01-26T13:05:50Z","timestamp":1516971950000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Randomized Communication versus Partition Number"],"prefix":"10.1145","volume":"10","author":[{"given":"Mika","family":"G\u00f6\u00f6s","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T. S.","family":"Jayram","sequence":"additional","affiliation":[{"name":"IBM Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[{"name":"University of Toronto, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Watson","sequence":"additional","affiliation":[{"name":"University of Memphis, Memphis, TN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808742"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897524"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982449"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.66"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056116"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11611257_13"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.05.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938517"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488629"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2347282"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746548"},{"key":"e_1_2_1_14_1","unstructured":"Mark Braverman and Omri Weinstein. 2015. Personal communication.  Mark Braverman and Omri Weinstein. 2015. Personal communication."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716307"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_43"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.69"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"Randomized communication vs. partition number. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","volume":"52","author":"G\u00f6\u00f6s Mika","year":"2017","unstructured":"Mika G\u00f6\u00f6s , T. S. Jayram , Toniann Pitassi , and Thomas Watson . 2017 . Randomized communication vs. partition number. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917) . Schloss Dagstuhl , 52 : 1 -- 52 :15. Mika G\u00f6\u00f6s, T. S. Jayram, Toniann Pitassi, and Thomas Watson. 2017. Randomized communication vs. partition number. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917). Schloss Dagstuhl, 52:1--52:15.","journal-title":"Schloss Dagstuhl"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M103145X"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.020"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.39"},{"volume-title":"Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics","author":"Jukna Stasys","key":"e_1_2_1_26_1","unstructured":"Stasys Jukna . 2012. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics , Vol. 27 . Springer . Stasys Jukna. 2012. Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics, Vol. 27. Springer."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_62"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/130928273"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_58"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM\u201915)","author":"Kothari Robin","year":"2015","unstructured":"Robin Kothari , David Racicot-Desloges , and Miklos Santha . 2015 . Separating decision tree complexity from subcube partition complexity . In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM\u201915) . Schloss Dagstuhl, 915--930. Robin Kothari, David Racicot-Desloges, and Miklos Santha. 2015. Separating decision tree complexity from subcube partition complexity. In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM\u201915). Schloss Dagstuhl, 915--930."},{"key":"e_1_2_1_31_1","volume-title":"Cited in {36}","author":"Kushilevitz Eyal","year":"1994","unstructured":"Eyal Kushilevitz . 1994. Unpublished. ( 1994 ). Cited in {36} . Eyal Kushilevitz. 1994. Unpublished. (1994). Cited in {36}."},{"volume-title":"Communication Complexity","author":"Kushilevitz Eyal","key":"e_1_2_1_32_1","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-010-0292-2"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21924"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 35th Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915)","author":"Mukhopadhyay Sagnik","year":"2015","unstructured":"Sagnik Mukhopadhyay and Swagato Sanyal . 2015 . Towards better separation between deterministic and randomized query complexity . In Proceedings of the 35th Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915) . Schloss Dagstuhl, 206--220. Sagnik Mukhopadhyay and Swagato Sanyal. 2015. Towards better separation between deterministic and randomized query complexity. In Proceedings of the 35th Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS\u201915). Schloss Dagstuhl, 206--220."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192527"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM\u201917)","author":"Watson Thomas","year":"2017","unstructured":"Thomas Watson . 2017 . Communication complexity of statistical distance . In Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM\u201917) . Schloss Dagstuhl, 49:1--49:10. Thomas Watson. 2017. Communication complexity of statistical distance. In Proceedings of the 21st International Workshop on Randomization and Computation (RANDOM\u201917). Schloss Dagstuhl, 49:1--49:10."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170711","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170711","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170711","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:58Z","timestamp":1750213618000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170711"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,24]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3170711"],"URL":"https:\/\/doi.org\/10.1145\/3170711","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,1,24]]},"assertion":[{"value":"2017-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}