{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:17:37Z","timestamp":1763468257094},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_41","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"506-516","source":"Crossref","is-referenced-by-count":3,"title":["Relative Discrepancy Does not Separate Information and Communication Complexity"],"prefix":"10.1007","author":[{"given":"Lila","family":"Fontes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Jain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iordanis","family":"Kerenidis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophie","family":"Laplante","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Lauri\u00e8re","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"10","key":"41_CR1","doi-asserted-by":"publisher","first-page":"6058","DOI":"10.1109\/TIT.2014.2347282","volume":"60","author":"M Braverman","year":"2014","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. IEEE Transactions on Information Theory 60(10), 6058\u20136069 (2014)","journal-title":"IEEE Transactions on Information Theory"},{"key":"41_CR2","volume-title":"The transmission of information, Technical Report 65, Research Laboratory for Electronics","author":"RM Fano","year":"1949","unstructured":"Fano, R.M.: The transmission of information, Technical Report 65, Research Laboratory for Electronics. MIT, Cambridge (1949)"},{"key":"41_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1007\/3-540-45061-0_26","volume-title":"Automata, Languages and Programming","author":"R Jain","year":"2003","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: A direct sum theorem in communicationcomplexity via message compression. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 300\u2013315. Springer, Heidelberg (2003)"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"Shannon, C.E.: A Mathematical Theory of Computation. The Bell System Technical Journal 27, 379\u2013423, 623\u2013656 (1948)","DOI":"10.1002\/j.1538-7305.1948.tb00917.x"},{"key":"41_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Wirth, A., Yao, A., Shi, Y.: Informational complexity and the direct sum problem for simultaneous message complexity. In: FOCS, pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"41_CR6","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. In: CoRR, vol. abs\/0807.1267, pp. 285\u2013296 (2008)"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"Harsha, P., Jain, R., McAllester, D., Radhakrishnan, J.: The communication complexity of correlation. In: CCC, pp. 10\u201323 (2007)","DOI":"10.1109\/CCC.2007.32"},{"issue":"4","key":"41_CR8","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.jcss.2003.11.006","volume":"68","author":"Z Bar-Yossef","year":"2004","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., 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"},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. In: STOC, pp. 67\u201376 (2010)","DOI":"10.1145\/1806689.1806701"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Interactive information complexity. In: STOC, pp. 505\u2013524 (2012)","DOI":"10.1145\/2213977.2214025"},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Lower bounds by probabilistic arguments. In: FOCS, pp. 420\u2013428 (1983)","DOI":"10.1109\/SFCS.1983.30"},{"key":"41_CR12","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing (preliminary report). In: STOC, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"Ganor, A., Kol, G., Raz, R.: Exponential separation of information and communication. In: ECCC, vol. 21, p. 49 (2014)","DOI":"10.1109\/FOCS.2014.27"},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"Ganor, A., Kol, G., Raz, R.: Exponential separation of information and communication for boolean functions. In: ECCC, vol. 113 (2014)","DOI":"10.1109\/FOCS.2014.27"},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., Laplante, S., Lerays, V., Roland, J., Xiao, D.: Lower bounds on information complexity via zero-communication protocols and applications. In: FOCS, pp. 500\u2013509 (2012)","DOI":"10.1109\/FOCS.2012.68"},{"key":"41_CR16","doi-asserted-by":"crossref","unstructured":"Jain, R., Klauck, H.: The partition bound for classical communication complexity and query complexity. In: CCC, pp. 1\u201328 (2010)","DOI":"10.1109\/CCC.2010.31"},{"key":"41_CR17","unstructured":"Jain, R., Lee, T., Vishnoi, N.: A quadratically tight partition bound for classical communication complexity and query complexity. In: CoRR, vol. abs\/1401.4512 (2014)"},{"key":"41_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1007\/978-3-662-43948-7_43","volume-title":"Automata, Languages, and Programming","author":"D Gavinsky","year":"2014","unstructured":"Gavinsky, D., Lovett, S.: En route to the log-rank conjecture: new reductions and equivalent formulations. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 514\u2013524. Springer, Heidelberg (2014)"},{"key":"41_CR19","unstructured":"Fontes, L., Jain, R., Kerenidis, I., Laplante, S., Lauriere, M., Roland, J.: Relative Discrepancy does not separate Information and Communication Complexity (2015). \n                    http:\/\/eccc.hpi-web.de\/report\/2015\/028\/"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T06:50:43Z","timestamp":1559199043000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}