MULTIPARTY COMMUNICATION COMPLEXITY AND THRESHOLD CIRCUIT SIZE OF AC0

We prove an n(Omega(1))/4(k) lower bound on the randomized k-party communication complexity of depth 4 AC(0) functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first nontrivial lower bounds for general NOF multiparty communication complexity for any AC(0) function for omega(log log n) players. For nonconstant k the bounds are larger than all previous lower bounds for any AC(0) function even for simultaneous communication complexity. Our lower bounds imply the first superpolynomial lower bounds for the simulation of AC(0) by MAJ circle SYM circle AND circuits, showing that the well-known quasi-polynomial simulations of AC(0) by such circuits due to Allender (1989) and Yao (1990) are qualitatively optimal, even for formulas of small constant depth. We also exhibit a depth 5 formula in NPkcc - BPPkcc for k up to Theta(log n) and derive Omega(2(root log n/root k)) lower bound on the randomized k-party NOF communication complexity of set disjointness for up to Theta(log(1/3) n) 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 AC(0) functions.