{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T00:54:51Z","timestamp":1778028891603,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,6,30]],"date-time":"2015-06-30T00:00:00Z","timestamp":1435622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore Ministry of Education Tier 3 Grant"},{"name":"Core Grants of the Center for Quantum Technologies, Singapore"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,6,30]]},"abstract":"<jats:p>\n            We show two new direct product results in two different models of communication complexity. Our first result is in the one-way public-coin model. Let\n            <jats:italic>f \u2286 X \u00d7 Y \u00d7 Z<\/jats:italic>\n            be a relation and \u03f5 &gt; 0 be a constant. Let R\n            <jats:sup>1,pub<\/jats:sup>\n            <jats:sub>\u03f5<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            ) represent the communication complexity of\n            <jats:italic>f<\/jats:italic>\n            , with worst-case error \u03f5 in this model. We show that if for computing\n            <jats:italic>\n              f\n              <jats:sup>k<\/jats:sup>\n            <\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            independent copies of\n            <jats:italic>f<\/jats:italic>\n            ) in this model,\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            \u010b R\n            <jats:sup>1, pub<\/jats:sup>\n            <jats:sub>1\/3<\/jats:sub>\n            (\n            <jats:italic>f<\/jats:italic>\n            )) communication is used, then the success is exponentially small in\n            <jats:italic>k<\/jats:italic>\n            . We show a new tight characterization of communication complexity in this model which strengthens the tight characterization shown in Jain et al. [2008]. We use this new characterization to show our direct product result and this characterization may also be of independent interest.\n          <\/jats:p>\n          <jats:p>\n            Our second direct product result is in the model of two-way public-coin communication complexity. We show a direct product result for all relations in this model in terms of a new complexity measure that we define. Our new measure is a generalization to nonproduct distributions, of the two-way product subdistribution bound of Jain et al. [2008]. Our direct product result therefore generalizes to nonproduct distributions, their direct product result in terms of the two-way product subdistribution bound. As an application of our new direct product result, we reproduce (via completely different arguments) strong direct product result for the set-disjointness problem which was previously shown by Klauck [2010]. We show this by proving that our new complexity measure gives a tight lower bound of \u03a9(\n            <jats:italic>n<\/jats:italic>\n            ) for the set-disjointness problem on\n            <jats:italic>n<\/jats:italic>\n            -bit inputs (this strengthens the linear lower bound on the rectangle\/corruption bound for set-disjointness shown by Razborov [1992]). In addition, we show that many previously known direct product results in this model are uniformly implied and often strengthened by our result.\n          <\/jats:p>","DOI":"10.1145\/2699432","type":"journal-article","created":{"date-parts":[[2015,7,6]],"date-time":"2015-07-06T14:04:16Z","timestamp":1436191456000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["New Strong Direct Product Results in Communication Complexity"],"prefix":"10.1145","volume":"62","author":[{"given":"Rahul","family":"Jain","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. 209--218","author":"Bar-Yossef Ziv","unstructured":"Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , and D. Sivakumar . 2002. An information statistics approach to data stream and communication complexity . In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. 209--218 . Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. 2002. An information statistics approach to data stream and communication complexity. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. 209--218."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.45"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_20"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.85"},{"key":"e_1_2_1_8_1","unstructured":"Mark Braverman and Omri Weinstein. 2014. An interactive information odometer with applications. ECCC-TR14-047.  Mark Braverman and Omri Weinstein. 2014. An interactive information odometer with applications. ECCC-TR14-047."},{"key":"e_1_2_1_9_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"1991","unstructured":"Thomas M. Cover and Joy A . Thomas . 1991 . Elements of Information Theory. Wiley , New York. Thomas M. Cover and Joy A. Thomas. 1991. Elements of Information Theory. Wiley, New York."},{"key":"e_1_2_1_10_1","unstructured":"Ronald de Wolf. 2005. Random access codes direct product theorems and multiparty communication complexity. Unpublished manuscript incorporated into Ben-Aroya et al. {2008}.  Ronald de Wolf. 2005. Random access codes direct product theorems and multiparty communication complexity. Unpublished manuscript incorporated into Ben-Aroya et al. {2008}."},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Dmitry Gavinsky. 2008. On the role of shared entanglement. Quant. Inf. Comput. 8.   Dmitry Gavinsky. 2008. On the role of shared entanglement. Quant. Inf. Comput. 8.","DOI":"10.26421\/QIC8.1-2-6"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250852"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.28"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374462"},{"key":"e_1_2_1_16_1","volume-title":"Vishnoi","author":"Jain Rahul","year":"2014","unstructured":"Rahul Jain , Troy Lee , and Nisheeth K . Vishnoi . 2014 . A quadratically tight partition bound for classical communication complexity and query complexity. arXiv:1401.4512. Rahul Jain, Troy Lee, and Nisheeth K. Vishnoi. 2014. A quadratically tight partition bound for classical communication complexity and query complexity. arXiv:1401.4512."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.42"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652142"},{"key":"e_1_2_1_19_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 30th International Colloquium on Automata Languages and Programming","author":"Jain Rahul","unstructured":"Rahul Jain , Jaikumar Radhakrishnan , and Pranab Sen . 2003. A direct sum theorem in communication complexity via message compression . In Proceedings of the 30th International Colloquium on Automata Languages and Programming . Lecture Notes in Computer Science , vol. 2719 . Springer , Berlin , 300--315. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. 2003. A direct sum theorem in communication complexity via message compression. In Proceedings of the 30th International Colloquium on Automata Languages and Programming. Lecture Notes in Computer Science, vol. 2719. Springer, Berlin, 300--315."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.24"},{"key":"e_1_2_1_21_1","unstructured":"Rahul Jain and Penghui Yao. 2012. A strong direct product theorem in terms of the smooth rectangle bound. arXiv:1209.0263.  Rahul Jain and Penghui Yao. 2012. A strong direct product theorem in terms of the smooth rectangle bound. arXiv:1209.0263."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_32"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806702"},{"key":"e_1_2_1_24_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press , Cambridge, UK . http:\/\/www.cs.technion.ac.il\/&sim;eyalk\/book.html. Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, Cambridge, UK. http:\/\/www.cs.technion.ac.il\/&sim;eyalk\/book.html."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.25"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258620"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0175-x"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993643"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a007"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699432","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699432","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699432"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,30]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6,30]]}},"alternative-id":["10.1145\/2699432"],"URL":"https:\/\/doi.org\/10.1145\/2699432","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,30]]},"assertion":[{"value":"2011-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}