Linear systems modulo composites

-
Shachar Lovett, IAS
Fine Hall 224

Computation modulo composite numbers is much less understood than computation over primes; and sometimes surprisingly much more powerful. A positive example is that the best construction of locally decodable codes known today heavily relies on computations modulo composites. A negative one if that while strong lower bounds are known for constant-depth circuits using $AND$, $OR$ and $MOD_5$ gates, no such lower bounds are known if the $MOD_5$ gates are replaced by $MOD_6$ gates. We consider in this work a restricted model of computation: linear systems modulo composites. This model was explicitly given by Beigel and Maciel (Complexity 97) as a barrier towards proving lowers bounds for computation modulo composites (i.e. ACC0). We completely resolve their problem in this work. Fix a modulus $M$.  A system of linear constraints in boolean variables $x_1,..,x_n \mod M$ has the following form: a linear equation is a constraint of the form $a_1 x_1 + ... + a_n x_n (\mod M) \in A$, where the variables $x_1,...,x_n$ are boolean, the coefficients $a_1,...,a_n$ are elements of $Z_M$, and $A$ is a subset of $Z_M$. A linear system is a set of linear constraints. We prove that any such system has exponentially small correlation with the $MOD_q$ function, where $m,q$ are co-prime. To this end we prove structural results on the accepting sets of such systems. This problem can be relatively easy solved for prime $M$ using Fourier analysis; however for composite $M$ these techniques break down. Recently, Chattopadhyay and Wigderson (FOCS'09) proved correlation bounds when $M$ has two prime factors (e.g. for $M=6$). In this work we generalize their technique to handle arbitrary $M$, and in fact arbitrary Abelian groups instead of $Z_M$. 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$ for computing the $MOD_q$ function, when $m,q$ are co-prime. Joint work with Arkadev Chattopadhyay.