ECCC-Report TR11-048https://eccc.weizmann.ac.il/report/2011/048Comments and Revisions published for TR11-048en-usSun, 10 Apr 2011 01:10:03 +0300
Paper TR11-048
| Linear systems over abelian groups |
Arkadev Chattopadhyay,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2011/048We 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).Sun, 10 Apr 2011 01:10:03 +0300https://eccc.weizmann.ac.il/report/2011/048