2026-07-23T21:27:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6394 2024-03-06T10:38:09Z ddc:004 open_access

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time Karppa, Matti Kaski, Petteri Kohonen, Jukka Ó Catháin, Padraig correlation derandomization outlier similarity search expander graph 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matti Karppa and Petteri Kaski and Jukka Kohonen and Padraig Ó Catháin 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.52 urn:nbn:de:0030-drops-63944 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.52 eng https://creativecommons.org/licenses/by/3.0/legalcode