{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:26:50Z","timestamp":1725823610073},"publisher-location":"Berlin, Heidelberg","reference-count":23,"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_78","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"960-972","source":"Crossref","is-referenced-by-count":0,"title":["Amplification of One-Way Information Complexity via Codes and Noise Sensitivity"],"prefix":"10.1007","author":[{"given":"Marco","family":"Molinaro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigory","family":"Yaroslavtsev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"2","key":"78_CR1","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"157","author":"FM Ablayev","year":"1996","unstructured":"Ablayev, F.M.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci. 157(2), 139\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"78_CR2","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. J. Comput. Syst. Sci. 68(4), 702\u2013732 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"78_CR3","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1145\/502090.502097","volume":"48","author":"R Beals","year":"2001","unstructured":"Beals, R., Buhrman, H., Cleve, R., Mosca, M., de Wolf, R.: Quantum lower bounds by polynomials. J. ACM 48(4), 778\u2013797 (2001)","journal-title":"J. ACM"},{"unstructured":"Buhrman, H., Garc\u00eda-Soriano, D., Matsliah, A., de Wolf, R.: The non-adaptive query complexity of testing k-parities. Chicago J. Theor. Comput. Sci. (2013)","key":"78_CR4"},{"doi-asserted-by":"crossref","unstructured":"Cover, T.M., Thomas, J.A.: Elements of information theory (2. ed.). Wiley (2006)","key":"78_CR5","DOI":"10.1002\/047174882X"},{"key":"78_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-642-32512-0_44","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"Anirban Dasgupta","year":"2012","unstructured":"Dasgupta, Anirban, Kumar, Ravi, Sivakumar, D.: Sparse and lopsided set disjointness via information theory. In: Gupta, Anupam, Jansen, Klaus, Rolim, Jos\u00e9, Servedio, Rocco (eds.) APPROX 2012 and RANDOM 2012. LNCS, vol. 7408, pp. 517\u2013528. Springer, Heidelberg (2012)"},{"issue":"6","key":"78_CR7","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1214\/aop\/1176995384","volume":"6","author":"RM Dudley","year":"1978","unstructured":"Dudley, R.M.: Central limit theorems for empirical measures. The Annals of Probability 6(6), 899\u2013929 (1978)","journal-title":"The Annals of Probability"},{"issue":"1","key":"78_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","volume":"100","author":"D Haussler","year":"1992","unstructured":"Haussler, D.: Decision theoretic generalizations of the PAC model for neural net and other learning applications. Inform. Comput. 100(1), 78\u2013150 (1992)","journal-title":"Inform. Comput."},{"doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Woodruff, D.P.: Optimal bounds for johnson-lindenstrauss transforms and streaming problems with sub-constant error. In: SODA (2011)","key":"78_CR9","DOI":"10.1137\/1.9781611973082.1"},{"doi-asserted-by":"crossref","unstructured":"Kremer, I., Nisan, N., Ron, D.: On randomized one-round communication complexity. Computational Complexity, pp. 21\u201349 (1999)","key":"78_CR10","DOI":"10.1007\/s000370050018"},{"issue":"4","key":"78_CR11","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science 3(4), 263\u2013399 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"doi-asserted-by":"crossref","unstructured":"Lee, T., Zhang, S.: Composition theorem in communication complexity. In: ICALP (2010)","key":"78_CR12","DOI":"10.1007\/978-3-642-14165-2_41"},{"doi-asserted-by":"crossref","unstructured":"Molinaro, M., Woodruff, D.P., Yaroslavtsev, G.: Beating the direct sum theorem in communication complexity with implications for sketching. In: SODA (2013)","key":"78_CR13","DOI":"10.1137\/1.9781611973105.125"},{"key":"78_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"issue":"2","key":"78_CR15","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2), 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Newman, I., Szegedy, M.: Public vs. private coin flips in one round communication games (extended abstract). In: STOC (1996)","key":"78_CR16","DOI":"10.1145\/237814.238004"},{"key":"78_CR17","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of boolean functions as real polynomials. Computational Complexity 4, 301\u2013313 (1994)","journal-title":"Computational Complexity"},{"unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press (2014)","key":"78_CR18"},{"issue":"2","key":"78_CR19","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Sipser, M.: Communication complexity. J. Comput. Syst. Sci. 28(2), 260\u2013269 (1984)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Saglam, M., Tardos, G.: On the communication complexity of sparse set disjointness and exists-equal problems. In: FOCS (2013)","key":"78_CR20","DOI":"10.1109\/FOCS.2013.78"},{"issue":"6","key":"78_CR21","doi-asserted-by":"publisher","first-page":"1969","DOI":"10.1137\/080733644","volume":"40","author":"A Sherstov","year":"2011","unstructured":"Sherstov, A.: The pattern matrix method. SIAM J. Comput. 40(6), 1969\u20132000 (2011)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: The average-case complexity of counting distinct elements. In: ICDT (2009)","key":"78_CR22","DOI":"10.1145\/1514894.1514928"},{"doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Lower bounds by probabilistic arguments (extended abstract). In: FOCS (1983)","key":"78_CR23","DOI":"10.1109\/SFCS.1983.30"}],"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_78","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T07:07:33Z","timestamp":1559200053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_78"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_78","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}