Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem

DOI10.1145/2728167zbMath1333.68235OpenAlexW2263882035MaRDI QIDQ2796401

Gregory Valiant

Publication date: 24 March 2016

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2728167

zbMATH Keywords

correlationsnearest neighborlocality sensitive hashingmetric embeddingapproximate closest pairasymmetric embeddingslearning juntasparity with noise

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Measures of association (correlation, canonical correlation, etc.) (62H20) Learning and adaptive systems in artificial intelligence (68T05)

Related Items (11)

Unnamed Item ⋮ A new coding-based algorithm for finding closest pair of vectors ⋮ Detecting the large entries of a sparse covariance matrix in sub-quadratic time ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Index structures for fast similarity search for real-valued vectors. I ⋮ High-dimensional approximate \(r\)-nets ⋮ An improved algorithm for learning sparse parities in the presence of noise ⋮ Unnamed Item ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Point location in arrangements of hyperplanes
• Rectangular matrix multiplication revisited
• Learning functions of \(k\) relevant variables
• Foundations of multidimensional and metric data structures.
• Positive definite functions on spheres
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• New Algorithms for Learning in Presence of Errors
• On Noise-Tolerant Learning of Sparse Parities and Related Problems
• Efficient noise-tolerant learning from statistical queries
• On Agnostic Learning of Parities, Monomials, and Halfspaces
• Similarity estimation techniques from rounding algorithms
• Approximating the cut-norm via Grothendieck's inequality
• Entropy based nearest neighbor search in high dimensions
• A Randomized Algorithm for Closest-Point Queries
• Multidimensional binary search trees used for associative searching
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Learning with Errors over Rings
• Public-key cryptosystems from the worst-case shortest vector problem
• A sieve algorithm for the shortest lattice vector problem
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Locality-sensitive hashing scheme based on p-stable distributions
• Multiplying matrices faster than coppersmith-winograd
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Compressed matrix multiplication
• On lattices, learning with errors, random linear codes, and cryptography
• Noise-tolerant learning, the parity problem, and the statistical query model

This page was built for publication: Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem