Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

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

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

6 Citations (Scopus)
71 Downloads (Pure)


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 languageEnglish
Title of host publication24th Annual European Symposium on Algorithms
Subtitle of host publicationESA 2016, August 22–24, 2016, Aarhus, Denmark
EditorsPiotr Sankowski, Christos Zaroliagis
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages17
ISBN (Electronic)978-3-95977-015-6
Publication statusPublished - 22 Aug 2016
MoE publication typeA4 Conference publication
EventEuropean Symposium on Algorithms - Aarhus University, Aarhus, Denmark
Duration: 22 Aug 201624 Aug 2016
Conference number: 24

Publication series

NameLeibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
ISSN (Electronic)1868-8969


ConferenceEuropean Symposium on Algorithms
Abbreviated titleESA
Internet address


  • correlation
  • derandomization
  • outlier
  • similarity search
  • expander graph


Dive into the research topics of 'Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time'. Together they form a unique fingerprint.

Cite this