Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time

DOI10.1007/S00453-020-00727-1zbMath1477.68533DBLPjournals/algorithmica/KarppaKKC20OpenAlexW2963088608WikidataQ100762403 ScholiaQ100762403MaRDI QIDQ2205636

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

Publication date: 21 October 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00727-1

zbMATH Keywords

correlationoutlierderandomizationsimilarity searchexpander graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of association (correlation, canonical correlation, etc.) (62H20) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• Problems and results in extremal combinatorics. I.
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Learning functions of \(k\) relevant variables
• Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
• Balls and Bins: Smaller Hash Families and Faster Evaluation
• Pseudorandom Generators for Combinatorial Shapes
• Almost Optimal Pseudorandom Generators for Spherical Caps
• Optimal Data-Dependent Hashing for Approximate Near Neighbors
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• On Computing Nearest Neighbors with Applications to Decoding of Binary Linear Codes
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• On Noise-Tolerant Learning of Sparse Parities and Related Problems
• New Algorithms for Finding Irreducible Polynomials Over Finite Fields
• Expander graphs and their applications
• Lower Bounds on Locality Sensitive Hashing
• On Agnostic Learning of Parities, Monomials, and Halfspaces
• Pseudorandomness via the Discrete Fourier Transform
• Locality-sensitive Hashing without False Negatives
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• A Faster Subquadratic Algorithm for Finding Outlier Correlations
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Probability Inequalities for Sums of Bounded Random Variables
• Beyond Locality-Sensitive Hashing
• Noise-tolerant learning, the parity problem, and the statistical query model
• On the complexity of \(k\)-SAT

This page was built for publication: Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time