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 fur Informatik GmbH, Dagstuhl Publishing |
Pages | 1-17 |
Number of pages | 17 |
ISBN (Electronic) | 978-3-95977-015-6 |
DOIs | |
Publication status | Published - 22 Aug 2016 |
MoE publication type | A4 Article in a 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 | Denmark |
City | Aarhus |
Period | 22/08/2016 → 24/08/2016 |
Internet address |
Keywords
- correlation
- derandomization
- outlier
- similarity search
- expander graph