{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T20:14:48Z","timestamp":1769631288076,"version":"3.49.0"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,12,9]],"date-time":"2016-12-09T00:00:00Z","timestamp":1481241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore Ministry of Education via Academic Research Fund Tier 3","award":["MOE2012-T3-1-009"],"award-info":[{"award-number":["MOE2012-T3-1-009"]}]},{"DOI":"10.13039\/100011102","name":"European Union Seventh Framework Programme","doi-asserted-by":"crossref","award":["600700 (QALGO)"],"award-info":[{"award-number":["600700 (QALGO)"]}],"id":[{"id":"10.13039\/100011102","id-type":"DOI","asserted-by":"crossref"}]},{"name":"French ANR Blanc project RDAM","award":["ANR-12-BS02-005"],"award-info":[{"award-number":["ANR-12-BS02-005"]}]},{"name":"Belgian ARC project COPHYMA"},{"name":"Center for Quantum Technologies and Young Researcher Award"},{"name":"European Union CHIST-ERA grant DIQIP"},{"name":"ERC project QCC"},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"<jats:p>Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Ganor et al. [2014] recently provided such a separation in the distributional case for a specific input distribution. We show that in the non-distributional setting, the relative discrepancy bound is smaller than the information complexity; hence, it cannot separate information and communication complexity. In addition, in the distributional case, we provide a linear program formulation for relative discrepancy and relate it to variants of the partition bound, resolving also an open question regarding the relation of the partition bound and information complexity. Last, we prove the equivalence between the adaptive relative discrepancy and the public-coin partition, implying that the logarithm of the adaptive relative discrepancy bound is quadratically tight with respect to communication.<\/jats:p>","DOI":"10.1145\/2967605","type":"journal-article","created":{"date-parts":[[2016,12,9]],"date-time":"2016-12-09T17:26:14Z","timestamp":1481304374000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Relative Discrepancy Does Not Separate Information and Communication Complexity"],"prefix":"10.1145","volume":"9","author":[{"given":"Lila","family":"Fontes","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Diderot, LIAFA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Jain","sequence":"additional","affiliation":[{"name":"CQT, National University of Singapore and MajuLab, CNRS-UNS-NUS-NTU International Joint Research Unit, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iordanis","family":"Kerenidis","sequence":"additional","affiliation":[{"name":"CNRS, Universit\u00e9 Paris-Diderot, LIAFA, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophie","family":"Laplante","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Diderot, LIAFA, PARIS Cedex"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Lauri\u00e8re","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Diderot, LIAFA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles (ULB), QuIC, Ecole Polytechnique de Bruxelles, Brussels, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806701"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214025"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875561"},{"key":"e_1_2_1_6_1","volume-title":"Thomas","author":"Cover Thomas M.","year":"1991","unstructured":"Thomas M. Cover and Joy A . Thomas . 1991 . Elements of Information Theory. Wiley-Interscience , New York. 542 pages. Thomas M. Cover and Joy A. Thomas. 1991. Elements of Information Theory. Wiley-Interscience, New York. 542 pages."},{"key":"e_1_2_1_8_1","first-page":"49","article-title":"Exponential separation of information and communication","volume":"21","author":"Ganor Anat","year":"2014","unstructured":"Anat Ganor , Gillat Kol , and Ran Raz . 2014 a. Exponential separation of information and communication . Electronic Colloquium on Computational Complexity 21 (2014), 49 . Retrieved from http:\/\/eccc.hpi-web.de\/report\/2014\/049. Anat Ganor, Gillat Kol, and Ran Raz. 2014a. Exponential separation of information and communication. Electronic Colloquium on Computational Complexity 21 (2014), 49. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2014\/049.","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_2_1_9_1","volume-title":"Electronic Colloquium on Computational Complexity","volume":"113","author":"Ganor Anat","year":"2014","unstructured":"Anat Ganor , Gillat Kol , and Ran Raz . 2014 b. Exponential separation of information and communication for boolean functions . In Electronic Colloquium on Computational Complexity , Vol. 113 . Retrieved from http:\/\/eccc.hpi-web.de\/report\/ 2014\/113\/. Anat Ganor, Gillat Kol, and Ran Raz. 2014b. Exponential separation of information and communication for boolean functions. In Electronic Colloquium on Computational Complexity, Vol. 113. Retrieved from http:\/\/eccc.hpi-web.de\/report\/2014\/113\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897535"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_43"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.32"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_2_1_14_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. CoRR abs\/1401.4512 (2014). http:\/\/arxiv.org\/abs\/1401.4512. Rahul Jain, Troy Lee, and Nisheeth K. Vishnoi. 2014. A quadratically tight partition bound for classical communication complexity and query complexity. CoRR abs\/1401.4512 (2014). http:\/\/arxiv.org\/abs\/1401.4512."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759242"},{"key":"e_1_2_1_16_1","volume-title":"Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR abs\/0807.1267","author":"Jain Rahul","year":"2008","unstructured":"Rahul Jain , Jaikumar Radhakrishnan , and Pranab Sen . 2008. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR abs\/0807.1267 ( 2008 ), 285--296. http:\/\/arxiv.org\/abs\/0807.1267. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. 2008. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR abs\/0807.1267 (2008), 285--296. http:\/\/arxiv.org\/abs\/0807.1267."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.68"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.30"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2967605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2967605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:49:57Z","timestamp":1750218597000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2967605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,9]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/2967605"],"URL":"https:\/\/doi.org\/10.1145\/2967605","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,9]]},"assertion":[{"value":"2015-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}