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 non-trivial lower bounds for general NOF multiparty communication complexity for any AC$^0$ function for $\omega(\log\log n)$ players. For non-constant $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-SYMM-AND circuits,
showing that the well-known quasipolynomial 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 NPc-BPPc for $k$ up to $\Theta(\log n)$ and derive
$\Omega(2^{\sqrt{\log n}/\sqrt{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.
Improved threshold circuit lower bound (Section 6).
We prove an $n^{\Omega(1)}/4^k$ lower bound on the randomized $k$-party communication complexity of depth 4 $\sf{AC}^0$ functions in the number-on-forehead (NOF) model for up to $\Theta(\log n)$ players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any $\sf{AC}^0$ function for $\omega(\log\log n)$ players. For non-constant $k$ the bounds are larger than all previous lower bounds for any $\sf{AC}^0$ function even for simultaneous communication complexity.
Our lower bounds imply the first superpolynomial lower bounds for the simulation of $\sf{AC}^0$ by $\sf{MAJ\circ SYMM\circ AND}$ circuits, showing that the well-known quasipolynomial simulations of $\sf{AC}^0$ by such circuits are qualitatively optimal, even for formulas of small constant depth.
We also exhibit a depth 5 formula in $\cl{NP}^{cc}_k-\cl{BPP}^{cc}_k$ for $k$ up to $\Theta(\log n)$ and derive an $\Omega(2^{\sqrt{\log n}/\sqrt{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 $\sf{AC}^0$ functions.
We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For non-constant 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 super-polynomial lower bounds for the simulation of AC^0 by general MAJ-SYMM-AND circuits, showing that the well-known quasi-polynomial simulations of AC^0 by such circuits are qualitatively optimal, even for read-once formulas of small constant depth.
We also exhibit a read-once depth 5 formula in NP^{cc}_k − BPP^{cc}_k for k up to Theta(log n) and derive an Omega(2^{(log n)^{1/2}/k^{1/2}}) lower bound on the randomized k-party NOF communication complexity of set disjointness for O(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 given by Lee and Shraibman and by Chattopadhyay and Ada (though the bound is not as strong as those previous bounds for o(log log n) players). In addition, we prove lower bounds and separations for read-once AC^0 formulas of smaller depth: a depth 4 function in NP^{cc)_k − BPP^{cc}_k for k = O(log n/ log log n) and a lower bound of n^{Omega(1/k)}/2^{O(k)} for depth 3 read-once AC^0 formulas.
