TR15-122 Authors: Shiteng Chen, Periklis Papakonstantinou

Publication: 29th July 2015 13:18

Downloads: 984

Keywords:

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the question posed by Green et al. [11] to which the $2^{-O\left( \frac{n}{d(n)} \right) }$ bound is a partial negative answer. We first show a $2^{-\Omega(n)}$ correlation upper bound that implies a $2^{\Omega(n)}$ circuit size lower bound. Then, through a reduction we obtain a $2^{-O(\frac{n}{d(n)})}$ correlation lower bound. In fact, the $2^{\Omega(n)}$ size lower bound is for $\text{MAJ}\circ\text{ANY}_{o(n)}\circ\text{AND}\circ\text{MOD}_r\circ\text{AND}_{O(1)}$ circuits, which can be of independent interest.