{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:47Z","timestamp":1763468087410,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642325113"},{"type":"electronic","value":"9783642325120"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_39","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"459-470","source":"Crossref","is-referenced-by-count":10,"title":["A Discrepancy Lower Bound for Information Complexity"],"prefix":"10.1007","author":[{"given":"Mark","family":"Braverman","sequence":"first","affiliation":[]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","first-page":"36","volume":"18","author":"G. Asharov","year":"2011","unstructured":"Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly-secure multiparty computation. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 36 (2011), http:\/\/dblp.uni-trier.de","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (2010)","DOI":"10.1145\/1806689.1806701"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1\u201310. ACM (1988)","DOI":"10.1145\/62212.62213"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. CoRR, abs\/1106.3595 (2010)","DOI":"10.1109\/FOCS.2011.86"},{"key":"39_CR5","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. Arxiv preprint arXiv:1106.3595 (2011)","DOI":"10.1109\/FOCS.2011.86"},{"key":"39_CR6","first-page":"123","volume":"18","author":"M. Braverman","year":"2011","unstructured":"Braverman, M.: Interactive information complexity. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 123 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"39_CR7","unstructured":"Braverman, M., Weinstein, O.: A discrepancy lower bound for information complexity. CoRR, abs\/1112.2000 (2011)"},{"issue":"6","key":"39_CR8","doi-asserted-by":"publisher","first-page":"1930","DOI":"10.1109\/18.265501","volume":"39","author":"R. Bar-Yehuda","year":"1993","unstructured":"Bar-Yehuda, R., Chor, B., Kushilevitz, E., Orlitsky, A.: Privacy, additional information and communication. IEEE Transactions on Information Theory\u00a039(6), 1930\u20131943 (1993)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"39_CR9","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\u00a068(4), 702\u2013732 (2004)","journal-title":"Journal of Computer and System Sciences"},{"key":"39_CR10","doi-asserted-by":"crossref","unstructured":"Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pp. 62\u201372. ACM (1989)","DOI":"10.1145\/73007.73013"},{"key":"39_CR11","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1109\/SFCS.2001.959901","volume-title":"Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science","author":"A. Chakrabarti","year":"2001","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Werner, B. (ed.) Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, October 14-17, pp. 270\u2013278. IEEE Computer Society, Los Alamitos (2001)"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Harsha, P., Jain, R., McAllester, D., Radhakrishnan, J.: The communication complexity of correlation. In: Twenty-Second Annual IEEE Conference on Computational Complexity, CCC 2007, pp. 10\u201323. IEEE (2007)","DOI":"10.1109\/CCC.2007.32"},{"key":"39_CR13","first-page":"1010","volume":"arXiv","author":"R. Jain","year":"2010","unstructured":"Jain, R.: A strong direct product theorem for two-way public coin communication complexity. Arxiv preprint arXiv:1010.0846 (2010)","journal-title":"Arxiv preprint"},{"key":"39_CR14","first-page":"0807","volume":"arXiv","author":"R. Jain","year":"2008","unstructured":"Jain, R., Sen, P., Radhakrishnan, J.: Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. Arxiv preprint arXiv:0807.1267 (2008)","journal-title":"Arxiv preprint"},{"issue":"1","key":"39_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s00224-003-1113-7","volume":"37","author":"H. Klauck","year":"2004","unstructured":"Klauck, H.: Quantum and approximate privacy. Theory Comput. Syst.\u00a037(1), 221\u2013246 (2004)","journal-title":"Theory Comput. Syst."},{"key":"39_CR16","doi-asserted-by":"crossref","unstructured":"Klauck, H.: A strong direct product theorem for disjointness. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, pp. 77\u201386. ACM (2010)","DOI":"10.1145\/1806689.1806702"},{"key":"39_CR17","first-page":"1204","volume":"arXiv","author":"I. Kerenidis","year":"2012","unstructured":"Kerenidis, I., Laplante, S., Lerays, V., Roland, J., Xiao, D.: Lower bounds on information complexity via zero-communication protocols and applications. Arxiv preprint arXiv:1204.1505 (2012)","journal-title":"Arxiv preprint"},{"key":"39_CR18","volume-title":"Communication complexity","author":"E. Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, New York (1997)"},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"Klauck, H., Spalek, R., De Wolf, R.: Quantum and classical strong direct product theorems and optimal time-space tradeoffs. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 12\u201321. IEEE (2004)","DOI":"10.1109\/FOCS.2004.52"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Lee, T., Shraibman, A., Spalek, R.: A direct product theorem for discrepancy. In: 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, pp. 71\u201380. IEEE (2008)","DOI":"10.1109\/CCC.2008.25"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, pp. 103\u2013111. ACM (1995)","DOI":"10.1145\/225058.225093"},{"issue":"2","key":"39_CR22","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0304-3975(92)90260-M","volume":"106","author":"A.A. Razborov","year":"1992","unstructured":"Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comput. Sci.\u00a0106(2), 385\u2013390 (1992)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"39_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-003-0175-x","volume":"12","author":"R. Shaltiel","year":"2003","unstructured":"Shaltiel, R.: Towards proving strong direct product theorems. Computational Complexity\u00a012(1), 1\u201322 (2003)","journal-title":"Computational Complexity"},{"key":"39_CR24","unstructured":"Smirnov, D.V.: Shannon\u2019s information methods for lower bounds for probabilistic communication complexity. Master\u2019s thesis, Moscow State University (1988)"},{"key":"39_CR25","first-page":"152","volume":"18","author":"E. Viola","year":"2011","unstructured":"Viola, E.: The communication complexity of addition. Electronic Colloquium on Computational Complexity (ECCC)\u00a018, 152 (2011)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"39_CR26","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"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:25:49Z","timestamp":1743823549000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}