e prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once AC^0 formulas having k-player randomized multiparty NOF communication complexity n^Omega(1) / 2^O(k). We show similar lower bounds for depth 4 read-once AC^0 formulas that have nondeterministic communication complexity O(log^2 n), yielding exponential separations between k-party nondeterministic and randomized communication complexity for AC^0 functions. As a consequence of the latter bound, we obtain an n^Omega(1/k) / 2^O(k) lower bound on the k-party NOF communication complexity of set disjointness. This is non-trivial for up to Theta(sqrt{log n}) players which is significantly larger than the up to Theta(loglog n) players allowed in the best previous lower bounds for multiparty set disjointness given by Lee and Shraibman [LS08] and by Chattopadhyay and Ada [CA08] (though our complexity bounds themselves are not as strong for o(loglog n) players). We derive these results by extending the k-party generalization in [CA08,LS08] of the pattern matrix method of Sherstov [Sh07,Sh08]. Using this technique, we derive a new sufficient criterion for strong communication complexity lower bounds based on functions having many diverse subfunctions that do not have good low-degree polynomial approximations. This criterion guarantees that such functions have orthogonalizing distributions that are "max-smooth" as opposed to the "min-smooth" orthogonalizing distributions used by Razborov and Sherstov [RS08] to analyze the sign-rank of AC^0.

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once AC^0 formulas having k-player randomized multiparty NOF communication complexity n^Omega(1) / 2^O(k). We show similar lower bounds for depth 4 read-once AC^0 formulas that have nondeterministic communication complexity O(log^2 n), yielding exponential separations between k-party nondeterministic and randomized communication complexity for AC^0 functions.

As a consequence of the latter bound, we obtain an n^Omega(1/k) / 2^O(k) lower bound on the k-party NOF communication complexity of set disjointness. This is non-trivial for up to Theta(sqrt{log n}) players which is significantly larger than the up to Theta(loglog n) players allowed in the best previous lower bounds for multiparty set disjointness given by Lee and Shraibman [LS08] and by Chattopadhyay and Ada [CA08] (though our complexity bounds themselves are not as strong for o(loglog n) players).

We derive these results by extending the k-party generalization in [CA08,LS08] of the pattern matrix method of Sherstov [Sh07,Sh08]. Using this technique, we derive a new sufficient criterion for strong communication complexity lower bounds based on functions having many diverse subfunctions that do not have good low-degree polynomial approximations. This criterion guarantees that such functions have orthogonalizing distributions that are "max-smooth" as opposed to the "min-smooth" orthogonalizing distributions used by Razborov and Sherstov [RS08] to analyze the sign-rank of AC^0.