Combinatorics Seminar
When: Sunday, March 27, 10am
Where: Schreiber 309
Speaker: Shachar Lovett, IAS, Princeton
Title: 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,..,x_n modulo M has the following form: a linear equation is a
constraint of the form $a_1 x_1 + ... + a_n x_n (modulo 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 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 such 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.