Linear Systems over Finite Abelian Groups
Arkadev Chattopadhyay, Shachar Lovett · 2011
We consider a system of linear constraints over any finite Abelian group G of the following form: ℓi(x1, ..., xn) ≡ ℓi,1x1+ ⋯ + ℓi,nxn∈ Aifor i=1, ..., N and each Ai⊂ G, ℓi,jis an element of G and xi'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 MODqboolean 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 MAJ ο AND ο ANY ο(1)ο MODmfor computing the MODqfunction, when m, q are co-prime. No superpolynomial lower bounds were known for such circuits for computing any explicit function. This completely solves an open problem posed by Beigel and Maciel (Complexity'97).