{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:18:58Z","timestamp":1774678738785,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T00:00:00Z","timestamp":1452556800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s00453-015-0112-9","type":"journal-article","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T20:11:00Z","timestamp":1452629460000},"page":"749-781","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Towards a Reverse Newman\u2019s Theorem in Interactive Information Complexity"],"prefix":"10.1007","volume":"76","author":[{"given":"Joshua","family":"Brody","sequence":"first","affiliation":[]},{"given":"Harry","family":"Buhrman","sequence":"additional","affiliation":[]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[]},{"given":"Bruno","family":"Loff","sequence":"additional","affiliation":[]},{"given":"Florian","family":"Speelman","sequence":"additional","affiliation":[]},{"given":"Nikolay","family":"Vereshchagin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,1,12]]},"reference":[{"key":"112_CR1","doi-asserted-by":"crossref","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. In: Proceedings of the 42nd STOC, pp. 67\u201376 (2010)","DOI":"10.1145\/1806689.1806701"},{"key":"112_CR2","doi-asserted-by":"crossref","unstructured":"Brody, J., Buhrman, H., Kouck\u00fd, M., Loff, B., Speelman, F., Vereshchagin, N.: Towards a reverse Newman\u2019s theorem in interactive information complexity. In: Proceedings of the 28th CCC, pp. 24\u201333 (2013)","DOI":"10.1109\/CCC.2013.12"},{"key":"112_CR3","doi-asserted-by":"crossref","unstructured":"Braverman, M., Garg, A.: Public vs private coin in bounded-round information. In: Proceedings of the 41st ICALP, pp. 502\u2013513 (2014)","DOI":"10.1007\/978-3-662-43948-7_42"},{"key":"112_CR4","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Kouck\u00fd, M., Vereshchagin, N.: Randomized individual communication complexity. In: Proceedings of the 23rd CCC, pp. 321\u2013331 (2008)","DOI":"10.1109\/CCC.2008.33"},{"key":"112_CR5","unstructured":"Bauer, B., Moran, S., Yehudayoff, A.: Internal compression of protocols to entropy. In: Proceedings of the 19th RANDOM, pp. 481\u2013496 (2015)"},{"key":"112_CR6","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. In: Proceedings of the 52nd STOC, pp. 748\u2013757 (2011)","DOI":"10.1109\/FOCS.2011.86"},{"key":"112_CR7","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A., Weinstein, O., Yehudayoff, A.: Direct product via round-preserving compression.In: Proceedings of the 40th ICALP, pp. 232\u2013243 (2013)","DOI":"10.1007\/978-3-642-39206-1_20"},{"issue":"4","key":"112_CR8","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 68(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"112_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.C.C.: Informational complexity and the direct sum problem for simultaneous message passing. In: Proceedings of the 42nd FOCS (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"issue":"5","key":"112_CR10","doi-asserted-by":"crossref","first-page":"1001","DOI":"10.1137\/S0097539791195877","volume":"23","author":"U Feige","year":"1994","unstructured":"Feige, U., Peleg, D., Raghavan, P.: Computing with noisy information. SIAM J. Comput. 23(5), 1001\u20131018 (1994)","journal-title":"SIAM J. Comput."},{"issue":"10","key":"112_CR11","first-page":"25","volume":"1","author":"P Hall","year":"1935","unstructured":"Hall, P.: On representatives of subsets. J. Lond. Math. Soc. 1(10), 25\u201330 (1935)","journal-title":"J. Lond. Math. Soc."},{"key":"112_CR12","doi-asserted-by":"crossref","unstructured":"Jain, R., Pereszlenyi, A., Yao, P.: A direct product theorem for bounded-round public-coin randomized communication complexity. In: Proceedings of the 53rd FOCS (2012)","DOI":"10.1109\/FOCS.2012.42"},{"key":"112_CR13","doi-asserted-by":"crossref","unstructured":"Jain, R., Radhakrishnan, J., Sen, P.: A direct sum theorem in communication complexity via message compression. In: Proceedings of the 30th ICALP (2003)","DOI":"10.1007\/3-540-45061-0_26"},{"key":"112_CR14","unstructured":"Kozachinsky, A.: On the role of private coins in unbounded-round information complexity. Technical Report TR14-062, ECCC (2014)"},{"key":"112_CR15","doi-asserted-by":"crossref","unstructured":"Kozachinsky, A.: On Slepian\u2013Wolf theorem with interaction. Unpublished, Private correspondence (2015)","DOI":"10.1007\/978-3-319-34171-2_15"},{"issue":"2","key":"112_CR16","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Inf. Process. Lett. 39(2), 67\u201371 (1991)","journal-title":"Inf. Process. Lett."},{"key":"112_CR17","unstructured":"Pankratov, D.: Direct sum questions in classical communication complexity. Master\u2019s thesis, University of Chicago (2012)"},{"key":"112_CR18","doi-asserted-by":"crossref","unstructured":"Renner, R., Wolf, S.: Simple and tight bounds for information reconciliation and privacy amplification. In: Advances in Cryptology\u2014ASIACRYPT 2005, volume 3788 of LNCS, pp. 199\u2013216 (2005)","DOI":"10.1007\/11593447_11"},{"key":"112_CR19","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1109\/TIT.1973.1055037","volume":"19","author":"D Slepian","year":"1973","unstructured":"Slepian, D., Wolf, J.K.: Noiseless coding of correlated information sources. IEEE Trans. Inf. Theory 19, 471\u2013480 (1973)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0112-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0112-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0112-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0112-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T14:16:25Z","timestamp":1567520185000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0112-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,12]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["112"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0112-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,12]]}}}