Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EXPONENTIAL SUM:
Reports tagged with exponential sum:
TR15-122 | 29th July 2015
Shiteng Chen, Periklis Papakonstantinou

#### Correlation lower bounds from correlation upper bounds

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

ISSN 1433-8092 | Imprint