## Abstract

We prove a 2^{-O(n/d(n))} lower bound on the correlation of MOD_{m} ○AND_{d(n)} and MOD_{r}, 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(n/d(n))} bound is a partial negative answer. We first show a 2^{-Ω(n)} correlation upper bound that implies a 2^{Ω(n)} circuit size lower bound. Then, through a reduction we obtain a 2^{-O(n/d(n))} correlation lower bound. In fact, the 2^{Ω(n)} size lower bound is for MAJ ○ ANY_{o(n)} ○ AND ○ MOD_{r} ○ AND_{O(1)} circuits, which is of independent interest.

Original language | English (US) |
---|---|

Pages (from-to) | 537-540 |

Number of pages | 4 |

Journal | Information Processing Letters |

Volume | 116 |

Issue number | 8 |

DOIs | |

State | Published - Aug 1 2016 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

## Keywords

- Circuit complexity
- Composite modulus
- Computational complexity
- Correlation