# Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time

arXiv: https://arxiv.org/abs/1606.05608 · HTML: https://mlsanity.com/paper/1606.05608/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2016.

## Built on by (most cited first, 1 of 1)

- [A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation](https://mlsanity.com/paper/2403.04726/) (2024)

## Abstract (arXiv)

We derandomize G. Valiant's [J. ACM 62 (2015) Art. 13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders in Reingold, Vadhan, and Wigderson [Ann. of Math. 155 (2002) 157--187]. We say that a function f:-1,1drightarrow-1,1D is a correlation amplifier with threshold 0≤τ≤ 1, error γ≥ 1, and strength p an even positive integer if for all pairs of vectors x,y∈-1,1d it holds that (i) |langle x,yrangle|<τ d implies |langle f(x),f(y)rangle|≤(τγ)pD; and (ii) |langle x,yrangle|≥τ d implies bigl(fraclangle x,yrangleγ dbigr)pD ≤langle f(x),f(y)rangle≤ bigl(fracγlangle x,yrangledbigr)pD.