Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

6 Sitaatiot (Scopus)
69 Lataukset (Pure)

Abstrakti

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.
AlkuperäiskieliEnglanti
Otsikko24th Annual European Symposium on Algorithms
AlaotsikkoESA 2016, August 22–24, 2016, Aarhus, Denmark
ToimittajatPiotr Sankowski, Christos Zaroliagis
KustantajaSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sivut1-17
Sivumäärä17
ISBN (elektroninen)978-3-95977-015-6
DOI - pysyväislinkit
TilaJulkaistu - 22 elok. 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaEuropean Symposium on Algorithms - Aarhus University, Aarhus, Tanska
Kesto: 22 elok. 201624 elok. 2016
Konferenssinumero: 24
http://conferences.au.dk/algo16/algo-frontpage/

Julkaisusarja

NimiLeibniz International Proceedings in Informatics
KustantajaSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
Vuosikerta57
ISSN (elektroninen)1868-8969

Conference

ConferenceEuropean Symposium on Algorithms
LyhennettäESA
Maa/AlueTanska
KaupunkiAarhus
Ajanjakso22/08/201624/08/2016
www-osoite

Sormenjälki

Sukella tutkimusaiheisiin 'Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä