{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:16Z","timestamp":1725728356966},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_19","type":"book-chapter","created":{"date-parts":[[2013,6,3]],"date-time":"2013-06-03T01:03:04Z","timestamp":1370221384000},"page":"212-223","source":"Crossref","is-referenced-by-count":0,"title":["Amortized Communication Complexity of an Equality Predicate"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Nikishkin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge Univ. Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"19_CR2","unstructured":"Chuklin, A.: Effective protocols for low-distance file synchronization. arXiv:1102.4712 (2011)"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1137\/0406043","volume":"6","author":"A. Orlitsky","year":"1993","unstructured":"Orlitsky, A.: Interactive communication of balanced distributions and of correlated files. SIAM Journal on Discrete Mathematics\u00a06, 548\u2013564 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"19_CR4","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom Generators for Spacebounded Computation. Combinatorica\u00a012(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"2","key":"19_CR5","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Widgerson, N.: Hardness vs. Randomness. Journal of Computer and System Sciences\u00a049(2), 149\u2013167 (1994)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"19_CR6","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF01200118","volume":"3","author":"R. Canetti","year":"1990","unstructured":"Canetti, R., Goldreich, O.: Bounds on Tradeoffs between Randomness and Communication Complexity. Computational Complexity\u00a03(2), 141\u2013167 (1990)","journal-title":"Computational Complexity"},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"L. Newman","year":"1991","unstructured":"Newman, L.: Private vs. Common Random Bits in Communication Complexity. Information Processing Letters\u00a039(2), 67\u201371 (1991)","journal-title":"Information Processing Letters"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Nisan, N., Widgerson, A.: Pseudorandomness for Network Algorithms. In: Proc. of the 26th ACM Symposium on Theory of Computing, pp. 356\u2013364 (1994)","DOI":"10.1145\/195058.195190"},{"key":"19_CR9","unstructured":"Smith, A.: Scrambling Adversarial Errors Using Few Random Bits, Optimal Information Reconciliation, and Better Private Codes. In: Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 395\u2013404 (2007)"},{"issue":"1","key":"19_CR10","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1006\/jcss.1996.0004","volume":"52","author":"N. Nisan","year":"1996","unstructured":"Nisan, N., Zukerman, D.: Randomness is Linear in Space. 1993 Journal of Computer and System Sciences\u00a052(1), 43\u201352 (1996)","journal-title":"1993 Journal of Computer and System Sciences"},{"issue":"4","key":"19_CR11","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1137\/S0097539792235864","volume":"24","author":"T. Feder","year":"1991","unstructured":"Feder, T., Kushilevitz, E., Naor, M., Nisan, N.: Amortized Communication Complexity. SIAM J. Comput.\u00a024(4), 736\u2013750 (1991)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"19_CR12","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0019-9958(60)90287-4","volume":"3","author":"R.C.M. Bose","year":"1960","unstructured":"Bose, R.C.M., Ray-Chaudhuri, D.K.: On A Class of Error Correcting Binary Group Codes. Information and Control\u00a03(1), 68\u201379 (1960)","journal-title":"Information and Control"},{"issue":"2","key":"19_CR13","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1109\/TIT.1968.1054109","volume":"14","author":"E.R. Berlekamp","year":"1967","unstructured":"Berlekamp, E.R.: Nonbinary BCH decoding. IEEE Transactions on in Information Theory\u00a014(2), 242 (1967)","journal-title":"IEEE Transactions on in Information Theory"},{"key":"19_CR14","unstructured":"Karchmer, M., Raz, R., Wigderson, A.: On Proving Super-Logarithmic Depth Lower Bounds via the Direct Sum in Communication Complexity. In: Proc. of 6th IEEE Structure in Complexity Theory, pp. 299\u2013304 (1991)"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Parnafes, I., Raz, R., Wigderson, A.: Direct Product Results and the GCD Problem, in Old and New Communication Models. In: STOC 1997 Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, pp. 363\u2013372 (1997)","DOI":"10.1145\/258533.258620"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.: Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"19_CR17","doi-asserted-by":"crossref","unstructured":"Sherstov, A.: Strong Direct Produce Theorems for Quantum Communication and Query Complexity. In: STOC 2011 Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 41\u201350 (2011)","DOI":"10.1145\/1993636.1993643"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T11:42:44Z","timestamp":1563104564000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}