The Randomized Communication Complexity of Set Disjointness

by Johan Håstad and Avi Wigderson

Theory of Computing, Volume 3(11), pp. 211-219, 2007

Bibliography with links to cited articles

[1] L. Babai, P. Frankl, and J. Simon: Complexity classes in communication complexity theory. In Proc. 27th FOCS, pp. 337-347. IEEE Computer Society, 1986.
[2] L. Babai and P. Kimmel: Randomized simultaneous messages: solution of a problem of yao in communication complexity. In Proc. 12th IEEE Symp. on Computational Complexity, pp. 239-246. IEEE Computer Society, 1997. [CCC:10.1109/CCC.1997.612319].
[3] Z. Bar-Yossef, T. S. Jayram, R. Kumar, and D. Sivakumar: Information statistics approach to data stream and communication complexity. J. of Computer and System Sciences, 68:702-732, 2004. [JCSS:10.1016/j.jcss.2003.11.006].
[4] S. Jukna: Extremal Combinatorics. Springer Verlag, 2001.
[5] B. Kalyanasundaram and G. Schnitger: The probabilistic communication complexity of set intersection. SIAM J. on Discrete Mathematics, 5:545-557, 1992. [SIDMA:10.1137/0405044].
[6] E. Kushilevitz and N. Nisan: Communication Complexity. Cambridge University Press, 1997.
[7] I. Newman: Private vs. common random bits in communication complexity. Information Processing Letters, 39:67-71, 1991. [IPL:10.1016/0020-0190(91)90157-D].
[8] I. Newman and M. Szegedy: Public vs. private coins flips in one round communication games. In Proc. 28th STOC, pp. 561-570. ACM Press, 1996. [STOC:237814.238004].
[9] N. Nisan and I. Segal: The communication requirements of efficient allocations and supporting lindhal prices. 2004. [ .pdf ]
[10] I. Parnafes, R. Raz, and A. Wigderson: Direct product results and the GCD problem in old and new communication models. In Proc. 29th STOC, pp. 363-372. ACM Press, 1997. [STOC:258533.258620].
[11] R. Raz and A. Wigderson: Monotone circuits for matching require linear depth. Journal of the ACM, 39:736-744, 1992. [JACM:146637.146684].
[12] A. A. Razborov: The distributional complexity of disjointness. Theoretical Computer Science, 106:385-390, 1992. [TCS:10.1016/0304-3975(92)90260-M].
[13] A. C.-C. Yao: Some complexity questions related to distributive computing. In Proc. 11th STOC, pp. 209-213. ACM Press, 1979. [STOC:800135.804414].

This file has been generated by bibtex2html 1.85.