\def\bibRCS{$Id: theory.bib,v 1.1 2004/11/12 08:00:09 beame Exp beame $}
  \makeatletter \@ifundefined{ccisdefined}{ \newcommand{\cc}[1]{\mbox{\it
  #1\/}} \newcommand{\ccisdefined}{} }{} \@ifundefined{journalfont}{
  \newcommand{\journalfont}{\it } }{} \makeatother
\begin{thebibliography}{10}{\itemsep =0pt}

\bibitem{ams:freq}
N.~Alon, Y.~Matias, and M.~Szegedy.
\newblock The space complexity of approximating the frequency moments.
\newblock {\em Journal of Computer and System Sciences}, 58(1):147--157, 1999.

\bibitem{bgkl03}
L.~Babai, A.~G{\'a}l, P.~G. Kimmel, and S.~V. Lokam.
\newblock Communication complexity of simultaneous messages.
\newblock {\em SIAM Journal on Computing}, 33(1):137--166, 2003.

\bibitem{bfs86}
L.~Babai, P.~Frankl, and J.~Simon.
\newblock Complexity classes in communication complexity theory.
\newblock In {\em 27th Annual Symposium on Foundations of Computer Science},
  pages 337--347, Toronto, Ontario, October 1986. IEEE.

\bibitem{bns89}
L.~Babai, N.~Nisan, and M.~Szegedy.
\newblock Multiparty protocols, pseudorandom generators for logspace, and
  time-space trade-offs.
\newblock {\em Journal of Computer and System Sciences}, 45(2):204--232,
  1992.

\bibitem{bjks:icost}
Z.~Bar-Yossef, T.S.~Jayram, R.~Kumar, and D.~Sivakumar.
\newblock Information theory methods in communication complexity.
\newblock In {\em Proceedings 17th Annual IEEE Conference on
  Computational Complexity}, pages 133--142, 2002.

\bibitem{bjks:conditionalicost}
Z.~Bar-Yossef, T.S.~Jayram, R.~Kumar, and D.~Sivakumar.
\newblock An information statistics approach to data stream and communication
  complexity.
\newblock {\em Journal of Computer and System Sciences}, 68(4):702--732, 2004.

\bibitem{bpsw}
P.~Beame, T.~Pitassi, N.~Segerlind, and A.~Wigderson.
\newblock Polynomial threshold proofs and multiparty communication complexity.
\newblock In preparation.

\bibitem{cks:disjoint}
A.~Chakrabarti, S.~Khot, and X.~Sun.
\newblock Near-optimal lower bounds on the multi-party communication complexity
  of set disjointness.
\newblock In {\em Proceedings 18th Annual IEEE Conference on
  Computational Complexity}, pages 107--117, 2003.

\bibitem{cswy:infocomplexity}
A.~Chakrabarti, Y.~Shi, A.~Wirth, and A.C-C. Yao.
\newblock Informational complexity and the direct sum problem for simultaneous
  message complexity.
\newblock In {\em Proceedings 42nd Annual Symposium on Foundations of Computer
  Science}, pages 270--278, 2001. IEEE.

\bibitem{cfl:multiparty}
A.~K.~Chandra, M.~L.~Furst, and R.~J.~Lipton.
\newblock Multi-party protocols.
\newblock In {\em Proceedings of the 15th Annual ACM Symposium on Theory
  of Computing}, pages 94--99, 1983.

\bibitem{ct:multiparty}
F.~R.~K. Chung and P.~Tetali.
\newblock Communication complexity and quasi-randomness.
\newblock {\em SIAM Journal on Discrete Mathematics}, 6(1):110--123, 1993.

\bibitem{jrs:directsum}
R.~Jain, J.~Radhakrishnan, and P.~Sen.
\newblock A direct sum theorem in communication complexity via message
  compression.
\newblock In {\em Automata, Languages, and Programming: 30th International
  Colloquium}, volume 2719 of {\em Lecture Notes in Computer Science}, pages
  300--315, 2003. Springer-Verlag.

\bibitem{ks87}
B.~Kalyanasundaram and G.~Schnitger.
\newblock The probabilistic communication complexity of set intersection.
\newblock In {\em Proceedings, Structure in Complexity Theory, Second Annual
  Conference}, pages 41--49, 1987. IEEE.

\bibitem{kkn:covers}
M.~Karchmer, E~ Kushilevitz, and N.~Nisan.
\newblock Fractional covers and communication complexity.
\newblock In {\em Proceedings, Structure in Complexity Theory, 7th Annual
  Conference}, pages 262--274, 1992. IEEE.

\bibitem{krw:directsum}
M.~Karchmer, R.~Raz, and A.~Wigderson.
\newblock Super-logarithmic depth lower bounds via direct sum in communication
  complexity.
\newblock {\em Computational Complexity}, 5:191--204, 1995.

\bibitem{klauck:rectangle}
H.~Klauck.
\newblock Rectangle size bounds and threshold covers in communication
  complexity.
\newblock In {\em Proceedings 18th Annual IEEE Conference on
  Computational Complexity}, pages 118--134, 2003.

\bibitem{kn97}
E.~Kushilevitz and N.~Nisan.
\newblock {\em Communication Complexity}.
\newblock Cambridge University Press, Cambridge, England ; New York, 1997.

\bibitem{nw:rounds}
N.~Nisan and A.~Wigderson.
\newblock Rounds in communication complexity revisited.
\newblock {\em SIAM Journal on Computing}, 22(1):211--219, 1993.

\bibitem{raz:multiparty}
R.~Raz.
\newblock The {BNS-Chung} criterion for multi-party communication complexity.
\newblock {\em Computational Complexity}, 9:113--122, 2000.

\bibitem{rw:matching}
R.~Raz and A.~Wigderson.
\newblock Monotone circuits for matching require linear depth.
\newblock {\em Journal of the ACM}, 39(3):736--744, July 1992.

\bibitem{razborov:disjointness}
A.~A.~Razborov.
\newblock On the distributional complexity of disjointness.
\newblock {\em Theoretical Computer Science}, 106(2):385--390, 1992.

\bibitem{ss:stream}
M.~E.~Saks and X.~Sun.
\newblock Space lower bounds for distance approximation in the data stream
  model.
\newblock In {\em Proceedings of the 34th Annual ACM Symposium on
  Theory of Computing}, pages 360--369, 2002.

\bibitem{shaltiel:directproduct}
R.~Shaltiel.
\newblock Towards proving strong direct product theorems.
\newblock In {\em Proceedings 16th Annual IEEE Conference on Computational
  Complexity}, pages 107--117, June 2001.

\end{thebibliography}