We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). Using this technique,we provide the first example of a function in AC^0 that has n^{Omega(1)} randomized k-party communication complexity for any constant k. This proves that depth-three circuits consisting of a Majority gate at the output, gates computing arbitrary symmetric function at the second layer and arbitrary gates of bounded fan-in at the base layer cannot simulate the circuit class AC^0 in subexponential size. This is in contrast to the classical result of Yao and Beigel-Tarui that shows that such depth-three circuits having only Majority gates can simulate the class ACC^0 in quasipolynomial size if the bottom fan-in is increased to poly-logarithmic size.

In the second part, we simplify the arguments in the breakthrough work of Bourgain for obtaining exponentially small upper bounds on the correlation between the boolean function MOD_q and functions represented by polynomials of small degree over Z_m, whem m,q >= 2 are coprime integers. Our calculation also shows similarity with techniques used to estimate discrepancy of functions in the multiparty communication setting. This results in a slight improvement of earlier estimates. It is known that such estimates imply that circuits of type MAJ.MOD_m.AND_{eps.log n} cannot compute the MOD_q function in sub-exponential size. It remains a major open question to determine if such circuits can simulate ACC^0 in poly size when the bottom fan-in is increased to poly-logarithmic size.

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function f defined by f(x)=1 iff P(x) in A, for all x in {0,1}^n. This improves the bound of exp(-\Omega(n/(m2^m)^d)) obtained in the breakthrough work of Bourgain and Green et.al. Our calculation is also slightly shorter than theirs.

Our result immediately implies the bound of exp(-\Omega(n/4^d)) for the special case of m=2. This bound was first reported in the recent work of Viola. Viola states that it is not clear how to extend their method to general m.