Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-122 | 29th July 2015 09:59

Correlation lower bounds from correlation upper bounds

RSS-Feed




TR15-122
Authors: Shiteng Chen, Periklis Papakonstantinou
Publication: 29th July 2015 13:18
Downloads: 823
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint