The One-Way Communication Complexity of Hamming Distance

by T. S. Jayram, Ravi Kumar, and D. Sivakumar

Theory of Computing, Volume 4(6), pp. 129-135, 2008

Bibliography with links to cited articles

[1] N. Alon, Y. Matias, and M. Szegedy: The space complexity of approximating the frequency moments. J. Comput. System Sci., 58(1):137-147, 1999. [JCSS:10.1006/jcss.1997.1545].
[2] Z. Bar-Yossef, T.S. Jayram, R. Kumar, and D. Sivakumar: Information theory methods in communication complexity. In Proc. 17th Annual IEEE Conf. Computational Complexity, pp. 93-102. IEEE, 2002. [CCC:10.1109/CCC.2002.1004344].
[3] Z. Bar-Yossef, R. Kumar, and D. Sivakumar: Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proc. 13th ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 623-632. SIAM, 2002. [SODA:545381.545464].
[4] M. X. Goemans and D. P. Williamson: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. [JACM:10.1145/227683.227684].
[5] I. Kremer, N. Nisan, and D. Ron: On randomized one-round communication complexity. Comput. Complexity, 8(1):21-49, 1999. [Springer:w5pccfda9jbhpgdj].
[6] E. Kushilevitz and N. Nisan: Communication Complexity. Cambridge University Press, 1997.
[7] E. Kushilevitz, R. Ostrovsky, and Y. Rabani: Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput., 30(2):457-474, 2000. [SICOMP:10.1137/S0097539798347177].
[8] C. McDiarmid: Probabilistic Methods for Algorithmic Discrete Mathematics, volume 16 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1998.
[9] I. Newman: Private vs. common random bits in communication complexity. Inform. Process. Lett., 39(2):67-71, 1991. [IPL:10.1016/0020-0190(91)90157-D].
[10] J. H. van Lint: Introduction to Coding Theory. Springer, 1999.
[11] D. Woodruff: Optimal space lower bounds for all frequency moments. In Proc. 15th Annual ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 167-175. SIAM, 2004. [SODA:982792.982817].
[12] D. Woodruff: Efficient and Private Distance Approximation in the Communication and Streaming Models. PhD thesis, MIT, 2007.

This file has been generated by bibtex2html 1.85.