{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T23:31:52Z","timestamp":1684971112650},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,5,19]],"date-time":"2016-05-19T00:00:00Z","timestamp":1463616000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s00453-016-0163-6","type":"journal-article","created":{"date-parts":[[2016,5,19]],"date-time":"2016-05-19T19:40:25Z","timestamp":1463686825000},"page":"796-845","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Certifying Equality With Limited Interaction"],"prefix":"10.1007","volume":"76","author":[{"given":"Joshua","family":"Brody","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Chakrabarti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ranganath","family":"Kondapally","sequence":"additional","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":[[2016,5,19]]},"reference":[{"issue":"2","key":"163_CR1","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0304-3975(95)00157-3","volume":"175","author":"F Ablayev","year":"1996","unstructured":"Ablayev, F.: Lower bounds for one-way probabilistic communication complexity and their application to space complexity. Theor. Comput. Sci. 175(2), 139\u2013159 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"163_CR2","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2567671","volume":"6","author":"A Ada","year":"2014","unstructured":"Ada, A., Chattopadhyay, A., Cook, S.A., Fontes, L., Kouck\u00fd, M., Pitassi, T.: The hardness of being private. ACM Trans. Comput. Theory 6(1), 1:1\u20131:24 (2014)","journal-title":"ACM Trans. Comput. Theory"},{"key":"163_CR3","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. System Sci. 58(1), 137\u2013147 (1999). Preliminary version. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, pp. 20\u201329 (1996)"},{"issue":"4","key":"163_CR4","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":"163_CR5","doi-asserted-by":"crossref","unstructured":"Barak, B., Braverman, M., Chen, X., Rao, A.: How to compress interactive communication. SIAM J. Comput. 42(3), 1327\u20131363 (2013). Preliminary version. In: Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, pp. 67\u201376 (2010)","DOI":"10.1137\/100811969"},{"key":"163_CR6","doi-asserted-by":"crossref","unstructured":"Braverman, M.: Interactive information complexity. In: Proceedings of the 44th Annual ACM Symposium on the Theory of Computing, pp. 505\u2013524 (2012)","DOI":"10.1145\/2213977.2214025"},{"key":"163_CR7","doi-asserted-by":"crossref","unstructured":"Braverman, M., Ellen, F., Oshman, R., Pitassi, T., Vaikuntanathan, V.: A tight bound for set disjointness in the message-passing model. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 668\u2013677 (2013)","DOI":"10.1109\/FOCS.2013.77"},{"key":"163_CR8","doi-asserted-by":"crossref","unstructured":"Braverman, M., Garg, A., Pankratov, D., Weinstein, O.: From information to exact communication. In: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pp. 151\u2013160 (2013)","DOI":"10.1145\/2488608.2488628"},{"key":"163_CR9","doi-asserted-by":"crossref","unstructured":"Braverman, M., Moitra, A.: An information complexity approach to extended formulations. In: Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pp. 161\u2013170 (2013)","DOI":"10.1145\/2488608.2488629"},{"key":"163_CR10","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A.: Information equals amortized communication. In: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pp. 748\u2013757 (2011)","DOI":"10.1109\/FOCS.2011.86"},{"key":"163_CR11","doi-asserted-by":"crossref","unstructured":"Braverman, M., Rao, A., Weinstein, O., Yehudayoff, A.: Direct product via round-preserving compression. In: Proceedings of the 40th International Colloquium on Automata, Languages and Programming, pp. 232\u2013243 (2013)","DOI":"10.1007\/978-3-642-39206-1_20"},{"key":"163_CR12","unstructured":"Brody, J., Chakrabarti, A., Kondapally, R.: Certifying equality with limited interaction. Technical Report TR12-153, ECCC (2012)"},{"key":"163_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2013.006","volume":"6","author":"Harry Buhrman","year":"2013","unstructured":"Buhrman, Harry, Garc\u0131a-Soriano, David, Matsliah, Arie, de Wolf, Ronald: The non-adaptive query complexity of testing k-parities. Chic. J. Theor. Comput. Sci. 6, 1\u201311 (2013)","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"163_CR14","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Cormode, G., Kondapally, R., McGregor, A.: Information cost tradeoffs for augmented index and streaming language recognition. SIAM J. Comput. 42(1), 61\u201383 (2013). Preliminary version. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, pp. 387\u2013396 (2010)","DOI":"10.1137\/100816481"},{"key":"163_CR15","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: Proceedings of the 18th Annual IEEE Conference on Computational Complexity, pp. 107\u2013117 (2003)","DOI":"10.1109\/CCC.2003.1214414"},{"key":"163_CR16","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Kondapally, R.: Everywhere-tight information cost tradeoffs for augmented index. In: Proceedings of the 15th International Workshop on Randomization and Approximation Techniques in Computer Science, pp. 448\u2013459 (2011)","DOI":"10.1007\/978-3-642-22935-0_38"},{"key":"163_CR17","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.C.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"163_CR18","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shubina, A.: Nearly private information retrieval. In: Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, volume 4708 of Lecture Notes in Computer Science, pp. 383\u2013393 (2007)","DOI":"10.1007\/978-3-540-74456-6_35"},{"key":"163_CR19","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2006","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory, 2nd edn. Wiley, Hoboken (2006)","edition":"2"},{"key":"163_CR20","doi-asserted-by":"crossref","unstructured":"Dasgupta, A., Kumar, R., Sivakumar, D.: Sparse and lopsided set disjointness via information theory. In: Proceedings of the 16th International Workshop on Randomization and Approximation Techniques in Computer Science, vol. 7409, pp. 517\u2013528 (2012)","DOI":"10.1007\/978-3-642-32512-0_44"},{"key":"163_CR21","doi-asserted-by":"crossref","unstructured":"Datar, M., Muthukrishnan, S.: Estimating rarity and similarity over data stream windows. In: Proceedings of the 10th Annual European Symposium on Algorithms, pp. 323\u2013334 (2002)","DOI":"10.1007\/3-540-45749-6_31"},{"issue":"5","key":"163_CR22","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/229459.229469","volume":"39","author":"R Fagin","year":"1996","unstructured":"Fagin, R., Naor, M., Winkler, P.: Comparing information without leaking it. Commun. ACM 39(5), 77\u201385 (1996)","journal-title":"Commun. ACM"},{"key":"163_CR23","doi-asserted-by":"crossref","unstructured":"Feder, T., Kushilevitz, E., Naor, M., Nisan, N.: Amortized communication complexity. SIAM J. Comput. 24(4), 736\u2013750 (1995). Preliminary version. In: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 239\u2013248 (1991)","DOI":"10.1137\/S0097539792235864"},{"key":"163_CR24","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $$O(1)$$ O ( 1 ) worst case access time. J. ACM 31(3), 538\u2013544 (1984). Preliminary version. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 165\u2013169 (1982)"},{"key":"163_CR25","first-page":"1","volume":"2004","author":"MJ Freedman","year":"2004","unstructured":"Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. Advances in Cryptology-EUROCRYPT 2004, 1\u201319 (2004)","journal-title":"Advances in Cryptology-EUROCRYPT"},{"key":"163_CR26","unstructured":"Freivalds, R.: Probabilistic machines can use less running time. In: IFIP Congress, pp. 839\u2013842 (1977)"},{"key":"163_CR27","unstructured":"Gronemeier, A.: Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness. In: Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, pp. 505\u2013516 (2009)"},{"key":"163_CR28","doi-asserted-by":"crossref","unstructured":"Harsha, P., Jain, R., McAllester, D., Radhakrishnan, J.: The communication complexity of correlation. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity, pp. 10\u201323 (2007)","DOI":"10.1109\/CCC.2007.32"},{"issue":"1","key":"163_CR29","doi-asserted-by":"crossref","first-page":"211","DOI":"10.4086\/toc.2007.v003a011","volume":"3","author":"J H\u00e5stad","year":"2007","unstructured":"H\u00e5stad, J., Wigderson, A.: The randomized communication complexity of set disjointness. Theory Comput. 3(1), 211\u2013219 (2007)","journal-title":"Theory Comput."},{"key":"163_CR30","first-page":"24","volume":"18","author":"R Jain","year":"2011","unstructured":"Jain, R.: New strong direct product results in communication complexity. Electron. Colloq. Comput. Complex. (ECCC) 18, 24 (2011)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"163_CR31","doi-asserted-by":"crossref","unstructured":"Jain, R., Pereszl\u00e9nyi, A., Yao, P.: A direct product theorem for the two-party bounded-round public-coin communication complexity. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 167\u2013176 (2012)","DOI":"10.1109\/FOCS.2012.42"},{"key":"163_CR32","unstructured":"Jain, R., Sen, P., Radhakrishnan, J.: Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. CoRR (2008). arXiv:0807.1267"},{"issue":"4","key":"163_CR33","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discret. Math. 5(4), 547\u2013557 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"163_CR34","doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: On the exact space complexity of sketching and streaming small norms. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1161\u20131178 (2010)","DOI":"10.1137\/1.9781611973075.93"},{"key":"163_CR35","unstructured":"Kerenidis, I., de\u00a0Wolf, R.: Exponential lower bound for 2-query locally decodable codes. J. Comput. Syst. Sci. 69(3), 395\u2013420 (2004). Preliminary version. In: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, pp. 106\u2013115 (2003)"},{"key":"163_CR36","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and approximate privacy. Theory Comput. Syst. 37(1), 221\u2013246 (2004). Preliminary version. In: Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science, pp. 335-346 (2002)","DOI":"10.1007\/s00224-003-1113-7"},{"key":"163_CR37","doi-asserted-by":"crossref","DOI":"10.1016\/S0065-2458(08)60342-3","volume-title":"Communication Complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)"},{"key":"163_CR38","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Weinreb, E.: The communication complexity of set-disjointness with small sets and 0-1 intersection. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 63\u201372 (2009)","DOI":"10.1109\/FOCS.2009.15"},{"key":"163_CR39","doi-asserted-by":"crossref","unstructured":"Magniez, F., Mathieu, C., Nayak, A.: Recognizing well-parenthesized expressions in the streaming model. In: Proceedings of the 41st Annual ACM Symposium on the Theory of Computing, pp. 261\u2013270 (2010)","DOI":"10.1145\/1806689.1806727"},{"key":"163_CR40","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Schmidt, E.M.: Las Vegas is better than determinism in VLSI and distributed computing (extended abstract). In: Proceedings of the 14th Annual ACM Symposium on the Theory of Computing, pp. 330\u2013337 (1982)","DOI":"10.1145\/800070.802208"},{"key":"163_CR41","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. J. Comput. Syst. Sci. 57(1), 37\u201349 (1998). Preliminary version. In: Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pp. 103\u2013111 (1995)"},{"key":"163_CR42","doi-asserted-by":"crossref","unstructured":"Molinaro, M., Woodruff, D., Yaroslavtsev, G.: Beating the direct sum theorem in communication complexity with implications for sketching. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (2013)","DOI":"10.1137\/1.9781611973105.125"},{"issue":"5","key":"163_CR43","doi-asserted-by":"crossref","first-page":"1254","DOI":"10.1137\/S0097539704383633","volume":"35","author":"M Naor","year":"2006","unstructured":"Naor, M., Pinkas, B.: Oblivious polynomial evaluation. SIAM J. Comput. 35(5), 1254\u20131281 (2006)","journal-title":"SIAM J. Comput."},{"key":"163_CR44","doi-asserted-by":"crossref","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 124\u2013133 (1999)","DOI":"10.1109\/SFFCS.1999.814608"},{"issue":"2","key":"163_CR45","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."},{"issue":"3","key":"163_CR46","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1137\/09075336X","volume":"40","author":"M P\u01cetra\u015fcu","year":"2011","unstructured":"P\u01cetra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. SIAM J. Comput. 40(3), 827\u2013847 (2011)","journal-title":"SIAM J. Comput."},{"key":"163_CR47","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Verbin, E., Zhang, Q.: Lower bounds for number-in-hand multiparty communication complexity, made easy. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 486\u2013501 (2012)","DOI":"10.1137\/1.9781611973099.42"},{"key":"163_CR48","doi-asserted-by":"crossref","unstructured":"Razborov, A.: On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385\u2013390 (1992). Preliminary version. In: Proceedings of the 17th International Colloquium on Automata, Languages and Programming, pp. 249\u2013253 (1990)","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"163_CR49","doi-asserted-by":"crossref","unstructured":"Saglam, M., Tardos, G.: On the communication complexity of sparse set disjointness and exists-equal problems. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pp. 678\u2013687 (2013)","DOI":"10.1109\/FOCS.2013.78"},{"key":"163_CR50","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Probabilistic computations: Towards a unified measure of complexity. In: Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"},{"key":"163_CR51","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Some complexity questions related to distributive computing. In: Proceedings of the 11th Annual ACM Symposium on the Theory of Computing, pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0163-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0163-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0163-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0163-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T21:16:29Z","timestamp":1567890989000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0163-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,19]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["163"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0163-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,19]]}}}