TR09-084 Authors: Arkadev Chattopadhyay, Avi Wigderson

Publication: 25th September 2009 16:12

Downloads: 1422

Keywords:

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.