Title: Linear Systems Over Finite Abelian Groups
Speaker: Shachar Lovett, Institute for Advanced Studies
Date: Wednesday, February 23, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider a system of linear constraints in boolean variables over any finite Abelian group $G$ of the following form: a linear equation is a constraint of the form $a_1 x_1 + ... + a_n x_n \in A$, where the variables x_1,...,x_n are boolean, the coefficients a_1,...,a_n are elements of G, and A is a subset of G. A linear system is a set of linear constraints. Our main result shows that the subset of the boolean cube that satisfies these constraints has exponentially small correlation with the MOD_k boolean function, whenever the order of $G$ and $k$ are co-prime numbers.
Our work extends the result of Chattopadhyay and Wigderson (FOCS'09) who obtain such a correlation bound when $G=Z_{pq}$ where $p,q$ are distinct prime factors. Our result yield the first exponential bounds on the size of boolean depth-four circuits of the form MAJ - AND - ANY_{O(1)} - MOD_m^A for computing the MOD_k function, when $m,k$ 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). Joint work with Arkadev Chattopadhyay.