{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:11:43Z","timestamp":1767139903374,"version":"build-2238731810"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T00:00:00Z","timestamp":1587340800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T00:00:00Z","timestamp":1587340800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00037-020-00192-w","type":"journal-article","created":{"date-parts":[[2020,4,19]],"date-time":"2020-04-19T22:02:25Z","timestamp":1587333745000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Communication Complexity with Small Advantage"],"prefix":"10.1007","volume":"29","author":[{"given":"Thomas","family":"Watson","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"issue":"6","key":"192_CR1","doi-asserted-by":"publisher","first-page":"1570","DOI":"10.1137\/S009753979935476","volume":"32","author":"Andris Ambainis","year":"2003","unstructured":"Ambainis, Andris, Schulman, Leonard, Ta-Shma, Amnon, Vazirani, Umesh, Wigderson, Avi: The Quantum Communication Complexity of Sampling. SIAM Journal on Computing 32(6), 1570\u20131585 (2003)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"192_CR2","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"TS Ziv Bar-Yossef","year":"2004","unstructured":"Ziv Bar-Yossef, T.S., Jayram, Ravi Kumar, Sivakumar, D.: An Information Statistics Approach to Data Stream and Communication Complexity. Journal of Computer and System Sciences 68(4), 702\u2013732 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"6","key":"192_CR3","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1137\/130938517","volume":"44","author":"Mark Braverman","year":"2015","unstructured":"Braverman, Mark: Interactive Information Complexity. SIAM Journal on Computing 44(6), 1698\u20131739 (2015)","journal-title":"SIAM Journal on Computing"},{"key":"192_CR4","doi-asserted-by":"crossref","unstructured":"Mark Braverman, Ankit Garg, Denis Pankratov & Omri Weinstein (2013). From Information to Exact Communication. In Proceedings of the 45th Symposium on Theory of Computing (STOC), 151\u2013160","DOI":"10.1145\/2488608.2488628"},{"key":"192_CR5","doi-asserted-by":"crossref","unstructured":"Mark Braverman & Ankur Moitra (2013). An Information Complexity Approach to Extended Formulations. In Proceedings of the 45th Symposium on Theory of Computing (STOC), 161\u2013170. ACM","DOI":"10.1145\/2488608.2488629"},{"issue":"10","key":"192_CR6","doi-asserted-by":"publisher","first-page":"6058","DOI":"10.1109\/TIT.2014.2347282","volume":"60","author":"Mark Braverman & Anup Rao","year":"2014","unstructured":"Mark Braverman & Anup Rao: Information Equals Amortized Communication. IEEE Transactions on Information Theory 60(10), 6058\u20136069 (2014)","journal-title":"IEEE Transactions on Information Theory"},{"key":"192_CR7","doi-asserted-by":"crossref","unstructured":"Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David Woodruff & Grigory Yaroslavtsev (2014). Beyond Set Disjointness: The Communication Complexity of Finding the Intersection. In Proceedings of the 33rd Symposium on Principles of Distributed Computing (PODC), 106\u2013113. ACM","DOI":"10.1145\/2611462.2611501"},{"issue":"3","key":"192_CR8","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1007\/s00453-016-0163-6","volume":"76","author":"Joshua Brody","year":"2016","unstructured":"Brody, Joshua, Chakrabarti, Amit, Kondapally, Ranganath, Woodruff, David, Yaroslavtsev, Grigory: Certifying Equality With Limited Interaction. Algorithmica 76(3), 796\u2013845 (2016)","journal-title":"Algorithmica"},{"issue":"5","key":"192_CR9","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/120861072","volume":"41","author":"Amit Chakrabarti & Oded Regev","year":"2012","unstructured":"Amit Chakrabarti & Oded Regev: An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. SIAM Journal on Computing 41(5), 1299\u20131317 (2012)","journal-title":"SIAM Journal on Computing"},{"key":"192_CR10","unstructured":"Arkadev Chattopadhyay & Sagnik Mukhopadhyay (2015). Tribes Is Hard in the Message Passing Model. In Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), 224\u2013237. Schloss Dagstuhl"},{"issue":"2","key":"192_CR11","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1137\/0217015","volume":"17","author":"Benny Chor & Oded Goldreich","year":"1988","unstructured":"Benny Chor & Oded Goldreich: Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity. SIAM Journal on Computing 17(2), 230\u2013261 (1988)","journal-title":"SIAM Journal on Computing"},{"key":"192_CR12","unstructured":"Thomas Cover & Joy Thomas (2006). Elements of Information Theory. Wiley."},{"key":"192_CR13","unstructured":"Mika G\u00f6\u00f6s & T. S. Jayram (2016). A Composition Theorem for Conical Juntas. In Proceedings of the 31st Computational Complexity Conference (CCC), 5:1\u20135:16. Schloss Dagstuhl"},{"key":"192_CR14","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s, T. S. Jayram, Toniann Pitassi & Thomas Watson (2018a). Randomized Communication vs. Partition Number. ACM Transactions on Computation Theory10(1), 4:1\u20134:20","DOI":"10.1145\/3170711"},{"issue":"5","key":"192_CR15","doi-asserted-by":"publisher","first-page":"1835","DOI":"10.1137\/15M103145X","volume":"45","author":"Mika G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, Mika, Lovett, Shachar, Meka, Raghu, Watson, Thomas, Zuckerman, David: Rectangles Are Nonnegative Juntas. SIAM Journal on Computing 45(5), 1835\u20131869 (2016)","journal-title":"SIAM Journal on Computing"},{"key":"192_CR16","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2017). Query-to-Communication Lifting for BPP. In Proceedings of the 58th Symposium on Foundations of Computer Science (FOCS), 132\u2013143. IEEE"},{"issue":"2","key":"192_CR17","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00037-018-0166-6","volume":"27","author":"Mika G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, Mika, Pitassi, Toniann, Watson, Thomas: The Landscape of Communication Complexity Classes. Computational Complexity 27(2), 245\u2013304 (2018b)","journal-title":"Computational Complexity"},{"issue":"9","key":"192_CR18","first-page":"1","volume":"12","author":"Mika G\u00f6\u00f6s & Thomas Watson","year":"2016","unstructured":"Mika G\u00f6\u00f6s & Thomas Watson: Communication Complexity of Set-Disjointness for All Probabilities. Theory of Computing 12(9), 1\u201323 (2016)","journal-title":"Theory of Computing"},{"key":"192_CR19","unstructured":"Prahladh Harsha & Rahul Jain (2013). A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound. In Proceedings of the 33rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 141\u2013152. Schloss Dagstuhl"},{"key":"192_CR20","unstructured":"Rahul Jain & Hartmut Klauck (2010). The Partition Bound for Classical Communication Complexity and Query Complexity. In Proceedings of the 25th Conference on Computational Complexity (CCC), 247\u2013258. IEEE"},{"key":"192_CR21","doi-asserted-by":"crossref","unstructured":"Rahul Jain, Hartmut Klauck & Shengyu Zhang (2010). Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas. In Proceedings of the 16th International Computing and Combinatorics Conference (COCOON), 54\u201359. Springer","DOI":"10.1007\/978-3-642-14031-0_8"},{"issue":"8","key":"192_CR22","doi-asserted-by":"publisher","first-page":"5171","DOI":"10.1109\/TIT.2013.2258372","volume":"59","author":"Rahul Jain","year":"2013","unstructured":"Jain, Rahul, Shi, Yaoyun, Wei, Zhaohui, Zhang, Shengyu: Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States. IEEE Transactions on Information Theory 59(8), 5171\u20135178 (2013)","journal-title":"IEEE Transactions on Information Theory"},{"key":"192_CR23","unstructured":"T.S. Jayram, Swastik Kopparty & Prasad Raghavendra (2009). On the Communication Complexity of Read-Once $${\\rm AC}^{0}$$ Formulae. In Proceedings of the 24th Conference on Computational Complexity (CCC), 329\u2013340. IEEE"},{"key":"192_CR24","doi-asserted-by":"crossref","unstructured":"T.S. Jayram, Ravi Kumar & D. Sivakumar (2003). Two Applications of Information Complexity. In Proceedings of the 35th Symposium on Theory of Computing (STOC), 673\u2013682. ACM","DOI":"10.1145\/780542.780640"},{"key":"192_CR25","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2003). Rectangle Size Bounds and Threshold Covers in Communication Complexity. In Proceedings of the 18th Conference on Computational Complexity (CCC), 118\u2013134. IEEE","DOI":"10.1109\/CCC.2003.1214415"},{"issue":"2","key":"192_CR26","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00037-010-0292-2","volume":"19","author":"Nikos Leonardos & Michael Saks","year":"2010","unstructured":"Nikos Leonardos & Michael Saks: Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Computational Complexity 19(2), 153\u2013181 (2010)","journal-title":"Computational Complexity"},{"issue":"2","key":"192_CR27","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"Alexander Razborov","year":"1992","unstructured":"Razborov, Alexander: On the Distributional Complexity of Disjointness. Theoretical Computer Science 106(2), 385\u2013390 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"5","key":"192_CR28","doi-asserted-by":"publisher","first-page":"1833","DOI":"10.1137\/080744037","volume":"39","author":"Alexander Razborov & Alexander Sherstov","year":"2010","unstructured":"Alexander Razborov & Alexander Sherstov: The Sign-Rank of $$\\rm AC^0$$. SIAM Journal on Computing 39(5), 1833\u20131855 (2010)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"192_CR29","doi-asserted-by":"publisher","first-page":"197","DOI":"10.4086\/toc.2012.v008a008","volume":"8","author":"Alexander Sherstov","year":"2012","unstructured":"Sherstov, Alexander: The Communication Complexity of Gap Hamming Distance. Theory of Computing 8(1), 197\u2013208 (2012)","journal-title":"Theory of Computing"},{"issue":"1","key":"192_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/cjtcs.2012.001","volume":"2012","author":"Thomas Vidick","year":"2012","unstructured":"Vidick, Thomas: A Concentration Inequality for the Overlap of a Vector on a Large Set, with Application to the Communication Complexity of the Gap-Hamming-Distance Problem. Chicago Journal of Theoretical Computer Science 2012(1), 1\u201312 (2012)","journal-title":"Chicago Journal of Theoretical Computer Science"},{"issue":"5","key":"192_CR31","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/120898553","volume":"43","author":"Thomas Watson","year":"2014","unstructured":"Watson, Thomas: Time Hierarchies for Sampling Distributions. SIAM Journal on Computing 43(5), 1709\u20131727 (2014)","journal-title":"SIAM Journal on Computing"},{"key":"192_CR32","unstructured":"Thomas Watson (2016). Nonnegative Rank vs. Binary Rank. Chicago Journal of Theoretical Computer Science2016(2), 1\u201313"},{"key":"192_CR33","unstructured":"Thomas Watson (2018). Communication Complexity with Small Advantage. In Proceedings of the 33rd Computational Complexity Conference (CCC), 9:1\u20139:17. Schloss Dagstuhl"}],"updated-by":[{"DOI":"10.1007\/s00037-020-00193-9","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000}}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00192-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-020-00192-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00192-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,19]],"date-time":"2021-04-19T20:30:54Z","timestamp":1618864254000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-020-00192-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,20]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["192"],"URL":"https:\/\/doi.org\/10.1007\/s00037-020-00192-w","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,20]]},"assertion":[{"value":"5 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 April 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2020","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Authors would like to correct the incorrect author references in the\nonline published article.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}