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.