ECCC-Report TR09-084https://eccc.weizmann.ac.il/report/2009/084Comments and Revisions published for TR09-084en-usFri, 25 Sep 2009 16:12:22 +0300
Paper TR09-084
| Linear systems over composite moduli |
Arkadev Chattopadhyay,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2009/084We 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. Fri, 25 Sep 2009 16:12:22 +0300https://eccc.weizmann.ac.il/report/2009/084