Correlation lower bounds from correlation upper bounds

Shiteng Chen; Periklis A. Papakonstantinou

doi:10.1016/j.ipl.2016.03.012

Correlation lower bounds from correlation upper bounds

Shiteng Chen
, Periklis A. Papakonstantinou

Rutgers Business School, Management & Information Systems

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1016/j.ipl.2016.03.012
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

Access to Document

10.1016/j.ipl.2016.03.012

Cite this

@article{9f71ad80ed0e407aaa8b43f53315de13,

title = "Correlation lower bounds from correlation upper bounds",

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.",

keywords = "Circuit complexity, Composite modulus, Computational complexity, Correlation",

author = "Shiteng Chen and Papakonstantinou, \{Periklis A.\}",

year = "2016",

month = aug,

day = "1",

doi = "10.1016/j.ipl.2016.03.012",

language = "English (US)",

volume = "116",

pages = "537--540",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "8",

}

TY - JOUR

T1 - Correlation lower bounds from correlation upper bounds

AU - Chen, Shiteng

AU - Papakonstantinou, Periklis A.

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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.

AB - 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.

KW - Circuit complexity

KW - Composite modulus

KW - Computational complexity

KW - Correlation

UR - https://www.scopus.com/pages/publications/84963491038

UR - https://www.scopus.com/pages/publications/84963491038#tab=citedBy

U2 - 10.1016/j.ipl.2016.03.012

DO - 10.1016/j.ipl.2016.03.012

M3 - Article

AN - SCOPUS:84963491038

SN - 0020-0190

VL - 116

SP - 537

EP - 540

JO - Information Processing Letters

JF - Information Processing Letters

IS - 8

ER -

Correlation lower bounds from correlation upper bounds

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this