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.