We prove an n¿(-1)/4klower bound on the randomized k-party communication complexity of depth 4 AC0functions in the number-on-forehead (NOF) model for up to ¿(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC0function for ¿ (log log n) players. For non-constant k the bounds are larger than all previous lower bounds for any AC0function even for simultaneous communication complexity. Our lower bounds imply the first superpolynomial lower bounds for the simulation of AC0by MAJ o SYMM o AND circuits, showing that the well-known quasipolynomial simulations of AC0by such circuits are qualitatively optimal, even for formulas of small constant depth. We also exhibit a depth 5 formula in NPkcc- BPPkccfor k up to ¿(log n) and derive an ¿(2¿(log n/ ¿(k))) lower bound on the randomized k-party NOF communication complexity of set disjointness for up to ¿(log1/3n) players which is significantly larger than the O (log log n) players allowed in the best previous lower bounds for multiparty set disjointness. We prove other strong results for depth 3 and 4 AC0functions.

We consider the read/write streams model, an extension of the standard data stream model in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. We show that any randomized read/write stream algorithm with a fixed number of streams and a sublogarithmic number of passes that produces a constant factor approximation of the k-th frequency moment Fkof an input sequence of length of at most N from {1, ..., N} requires space Omega(N1-4/k-delta) for any delta > 0. For comparison, it is known that with a single read-only data stream there is a randomized constant- factor approximation for Fkusing O(N1-2/k) space and that there is a deterministic algorithm computing Fkexactly using 3 read/write streams, O(log N) passes, and O(log N) space. Therefore, although the ability to manipulate multiple read/write streams can add substantial power to the data stream model, with a sub-logarithmic number of passes this does not significantly improve the ability to approximate higher frequency moments efficiently. Our lower bounds also apply to (1 + epsi)-approximations of Fkfor epsi ges 1/N.