ECCC-Report TR15-122https://eccc.weizmann.ac.il/report/2015/122Comments and Revisions published for TR15-122en-usWed, 29 Jul 2015 13:18:47 +0300
Paper TR15-122
| Correlation lower bounds from correlation upper bounds |
Shiteng Chen,
Periklis Papakonstantinou
https://eccc.weizmann.ac.il/report/2015/122We 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.
Wed, 29 Jul 2015 13:18:47 +0300https://eccc.weizmann.ac.il/report/2015/122