Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-084 | 24th September 2009 23:29

Linear systems over composite moduli


Authors: Arkadev Chattopadhyay, Avi Wigderson
Publication: 25th September 2009 16:12
Downloads: 1260


We study solution sets to systems of generalized linear equations of the following form:
$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,
where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite integer that is a product of two distinct primes, like 6. Our main technical result is that such solution sets have exponentially small correlation, i.e. $\exp\big(-\Omega(n)\big)$, with the boolean function $\MOD_q$, when $m$ and $q$ are relatively prime. This bound is independent of the number $t$ of equations.

This yields progress on limiting the power of constant-depth circuits with modular gates.
We derive the first exponential lower bound on the size of depth-three circuits of type $\text{MAJ} \circ \text{AND} \circ \text{MOD}_m^A$ (i.e. having a MAJORITY gate at the top, AND/OR gates at the middle layer and generalized $\MOD_m$
gates at the base) computing the function $\MOD_q$. This settles a decade-old open problem of Beigel and Maciel, for the case of such modulus $m$.

Our technique makes use of the work of Bourgain on estimating exponential sums involving a low-degree polynomial and ideas involving matrix rigidity from the work of Grigoriev and Razborov on arithmetic circuits over finite fields.

ISSN 1433-8092 | Imprint