License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.52
URN: urn:nbn:de:0030-drops-63944
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6394/
Go to the corresponding LIPIcs Volume Portal

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

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

pdf-format:
LIPIcs-ESA-2016-52.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{karppa_et_al:LIPIcs:2016:6394,
  author =	{Matti Karppa and Petteri Kaski and Jukka Kohonen and Padraig Ó Cath{\'a}in},
  title =	{{Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6394},
  URN =		{urn:nbn:de:0030-drops-63944},
  doi =		{10.4230/LIPIcs.ESA.2016.52},
  annote =	{Keywords: correlation, derandomization, outlier, similarity search, expander graph}
}

Keywords: correlation, derandomization, outlier, similarity search, expander graph
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI