Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Matti Karppa; Petteri Kaski; Jukka Kohonen; Padraig Ó Catháin

doi:10.4230/LIPIcs.ESA.2016.52

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Matti Karppa, Petteri Kaski, Jukka Kohonen, Padraig Ó Catháin

Aalto University

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

6 Citations (Scopus)

71 Downloads (Pure)

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.

Original language	English
Title of host publication	24th Annual European Symposium on Algorithms
Subtitle of host publication	ESA 2016, August 22–24, 2016, Aarhus, Denmark
Editors	Piotr Sankowski, Christos Zaroliagis
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-17
Number of pages	17
ISBN (Electronic)	978-3-95977-015-6
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2016.52
Publication status	Published - 22 Aug 2016
MoE publication type	A4 Conference publication
Event	European Symposium on Algorithms - Aarhus University, Aarhus, Denmark Duration: 22 Aug 2016 → 24 Aug 2016 Conference number: 24 http://conferences.au.dk/algo16/algo-frontpage/

Publication series

Name	Leibniz International Proceedings in Informatics
Publisher	Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Volume	57
ISSN (Electronic)	1868-8969

Conference

Conference	European Symposium on Algorithms
Abbreviated title	ESA
Country/Territory	Denmark
City	Aarhus
Period	22/08/2016 → 24/08/2016
Internet address	http://conferences.au.dk/algo16/algo-frontpage/

Keywords

correlation
derandomization
outlier
similarity search
expander graph

Access to Document

10.4230/LIPIcs.ESA.2016.52

LIPIcs-ESA-2016-52Final published version, 593 KBLicence: CC BY

Cite this

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 (pp. 1-17). Article 52 (Leibniz International Proceedings in Informatics; Vol. 57). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2016.52

Karppa, Matti ; Kaski, Petteri ; Kohonen, Jukka et al. / Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. 24th Annual European Symposium on Algorithms: ESA 2016, August 22–24, 2016, Aarhus, Denmark. editor / Piotr Sankowski ; Christos Zaroliagis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. pp. 1-17 (Leibniz International Proceedings in Informatics).

@inproceedings{3969c3dcb6e442efa08fd939053931e8,

title = "Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time",

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) ||| <= (tau*gamma)^p*D; and (ii) || >= tau*d implies (/gamma^d})^p*D <= <= (gamma*/d)^p*D.",

keywords = "correlation, derandomization, outlier, similarity search, expander graph",

author = "Matti Karppa and Petteri Kaski and Jukka Kohonen and {{\'O} Cath{\'a}in}, Padraig",

year = "2016",

month = aug,

day = "22",

doi = "10.4230/LIPIcs.ESA.2016.52",

language = "English",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--17",

editor = "Sankowski, {Piotr } and Zaroliagis, {Christos }",

booktitle = "24th Annual European Symposium on Algorithms",

address = "Germany",

note = "European Symposium on Algorithms , ESA ; Conference date: 22-08-2016 Through 24-08-2016",

url = "http://conferences.au.dk/algo16/algo-frontpage/",

}

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

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. / Karppa, Matti; Kaski, Petteri ; Kohonen, Jukka et al.
24th Annual European Symposium on Algorithms: ESA 2016, August 22–24, 2016, Aarhus, Denmark. ed. / Piotr Sankowski; Christos Zaroliagis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. p. 1-17 52 (Leibniz International Proceedings in Informatics; Vol. 57).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

AU - Karppa, Matti

AU - Kaski, Petteri

AU - Kohonen, Jukka

AU - Ó Catháin, Padraig

N1 - Conference code: 24

PY - 2016/8/22

Y1 - 2016/8/22

N2 - 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) ||| <= (tau*gamma)^p*D; and (ii) || >= tau*d implies (/gamma^d})^p*D <= <= (gamma*/d)^p*D.

AB - 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) ||| <= (tau*gamma)^p*D; and (ii) || >= tau*d implies (/gamma^d})^p*D <= <= (gamma*/d)^p*D.

KW - correlation

KW - derandomization

KW - outlier

KW - similarity search

KW - expander graph

UR - http://www.scopus.com/inward/record.url?scp=85012966908&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2016.52

DO - 10.4230/LIPIcs.ESA.2016.52

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics

SP - 1

EP - 17

BT - 24th Annual European Symposium on Algorithms

A2 - Sankowski, Piotr

A2 - Zaroliagis, Christos

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - European Symposium on Algorithms

Y2 - 22 August 2016 through 24 August 2016

ER -

Karppa M, Kaski P , Kohonen J, Ó Catháin P. Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time. In Sankowski P, Zaroliagis C, editors, 24th Annual European Symposium on Algorithms: ESA 2016, August 22–24, 2016, Aarhus, Denmark. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2016. p. 1-17. 52. (Leibniz International Proceedings in Informatics). doi: 10.4230/LIPIcs.ESA.2016.52

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this