Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
From MaRDI portal
Publication:2205636
DOI10.1007/s00453-020-00727-1zbMath1477.68533OpenAlexW2963088608WikidataQ100762403 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
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
