TR11-048 Authors: Arkadev Chattopadhyay, Shachar Lovett

Publication: 10th April 2011 01:10

Downloads: 3198

Keywords:

We consider a system of linear constraints over any finite Abelian group $G$ of the following form: $\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$ for $i=1,\ldots,t$ and each $A_i \subset G$, $\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean cube that satisfies these constraints has exponentially small correlation with the $\text{MOD}_q$ boolean function, when the order of $G$ and $q$ are co-prime numbers.

Our work extends the recent result of Chattopadhyay and Wigderson (FOCS'09) who obtain such a correlation bound for linear systems over cyclic groups whose order is a product of two distinct primes or has at most one prime factor. Our result also immediately yields the first exponential bounds on the size of boolean depth-four circuits of the form $\text{MAJ} \circ \text{AND} \circ \text{ANY}_{O(1)} \circ \text{MOD}_m$ for computing the $\text{MOD}_q$ function, when $m,q$ are co-prime. No superpolynomial lower bounds were known for such circuits for computing any explicit function.%, when $m$ had three or more distinct prime factors.

This completely solves an open problem posed by Beigel and Maciel (Complexity'97).