The Weizmann Institute of Science Faculty of Mathematics and Computer Science Foundations of Computer Science Seminar Seminar Room, Room 261, Ziskind Building on Monday, March 28, 2011 14:30 - 15:30 Shachar Lovett Institute of Advanced Study will speak on Linear systems modulo composites Abstract: 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 the problem in this work. Fix a modulus $M$. A system of linear constraints in boolean variables $x_1,\dots ,x_n$ modulo $M$ has the following form: a linear equation is a constraint of the form $a_1 x_1 + \cdots + a_n x_n (modulo\ M) \in A$, where the variables $x_1,\ldots,x_n$ are boolean, the coefficients $a_1,\ldots,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 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.