Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

摘要

We derandomize Valiant's (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. 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 ofcorrelation amplifiersbuilt via a family of zigzag-product expanders by Reingold et al. (Ann Math 155(1):157-187, 2002). We say that a functionf:{-1,1}(d) - {-1,1}(D) is acorrelation amplifier with threshold 0 = tau = 1, error gamma = 1, and strengthpan even positive integer if for all pairs of vectorsx, y is an element of {-1,1}(d) it holds that (i) vertical bar x,y vertical bar tau d implies vertical bar f(x),f(y)vertical bar; and (ii) vertical bar x,y vertical bar tau d implies implies ( x,y /gamma d)(p) D = f (x), f (y) = (gamma x,y /d)(p) D.