Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
17
Series
24th Annual European Symposium on Algorithms: ESA 2016, August 22–24, 2016, Aarhus, Denmark, pp. 1-17, Leibniz International Proceedings in Informatics ; Volume 57
Abstract
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,1}^d ->{-1,1}^D is a correlation amplifier with threshold 0 <= tau <= 1, error gamma >= 1, and strength p an even positive integer if for all pairs of vectors x,y in {-1,1}^d it holds that (i) |<x,y>|<tau d implies |<f(x),f(y)>| <= (tau*gamma)^p*D; and (ii) |<x,y>| >= tau*d implies (<x,y>/gamma^d})^p*D <= <f(x),f(y)> <= (gamma*<x,y>/d)^p*D.Description
Keywords
Other note
Citation
Karppa, M, Kaski, P, Kohonen, J & Ó Catháin, P 2016, Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. in P Sankowski & C Zaroliagis (eds), 24th Annual European Symposium on Algorithms : ESA 2016, August 22–24, 2016, Aarhus, Denmark., 52, Leibniz International Proceedings in Informatics, vol. 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-17, European Symposium on Algorithms, Aarhus, Denmark, 22/08/2016. https://doi.org/10.4230/LIPIcs.ESA.2016.52