Correlation lower bounds from correlation upper bounds

• Study limitations of correlation as asked by Green–Roy–Straubing.
• First lower bound on correlation for composite moduli.
• New two-step (lift and reduce) technique for proving correlation lower bounds.
• New circuit lower bound for circuits: MAJ∘ANYo(n)∘AND∘MOD∘ANDO(1)MAJ∘ANYo(n)∘AND∘MOD∘ANDO(1).

We prove a 2−O(nd(n)) lower bound on the correlation of MODm∘ANDd(n)MODm∘ANDd(n) and MODrMODr, where m, r are positive integers. This is the first non-trivial lower bound on the correlation of such functions for arbitrary m, r  . Our motivation is the question posed by Green et al., to which the 2−O(nd(n)) bound is a partial negative answer. We first show a 2−Ω(n)2−Ω(n) correlation upper bound that implies a 2Ω(n)2Ω(n) circuit size lower bound. Then, through a reduction we obtain a 2−O(nd(n)) correlation lower bound. In fact, the 2Ω(n)2Ω(n) size lower bound is for MAJ∘ANYo(n)∘AND∘MODr∘ANDO(1)MAJ∘ANYo(n)∘AND∘MODr∘ANDO(1) circuits, which is of independent interest.