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.

[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].