Consider a system of generalized linear equations over Z_m of the following form: l_i(x_1,...,x_n) in A_i for 1 \leq i \leq t, where each A_i is a subset of Z_m and m is a constant number like 6. We show that the boolean solution set of such a system has exponentially small correlation with the boolean MOD_q function, if m and q are co-prime. We obtain this result by combining ideas involving matrix rigidity from Grigoriev and Razborov (FOCS 98) with estimates of exponential sums by Bourgain (2005).

This immediately implies that depth-three circuits of type Majority of AND of MOD_m^A need exponential size to compute the MOD_q function. This is the first superpolynomial lower bound on the size of such circuits and settles an open problem due to Beigel and Maciel (Complexity 97).

Based on two works, one joint with Avi Wigderson and the other joint with Shachar Lovett.