Correlation lower bounds from correlation upper bounds

Research output: Contribution to journalArticlepeer-review

Abstract

We prove a 2-O(n/d(n)) lower bound on the correlation of MODm ○ANDd(n) and MODr, 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 ○ ANYo(n) ○ AND ○ MODr ○ ANDO(1) circuits, which is of independent interest.

Original languageEnglish (US)
Pages (from-to)537-540
Number of pages4
JournalInformation Processing Letters
Volume116
Issue number8
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Correlation lower bounds from correlation upper bounds'. Together they form a unique fingerprint.

Cite this