Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
From MaRDI portal
Recommendations
- A faster subquadratic algorithm for finding outlier correlations
- A Faster Subquadratic Algorithm for Finding Outlier Correlations
- A new algorithm for finding closest pair of vectors (extended abstract)
- An improved algorithm for learning sparse parities in the presence of noise
- On noise-tolerant learning of sparse parities and related problems
Cites work
- A Randomized Algorithm for Closest-Point Queries
- A sieve algorithm for the shortest lattice vector problem
- Approximating the cut-norm via Grothendieck's inequality
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
- Compressed matrix multiplication
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- Efficient noise-tolerant learning from statistical queries
- Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
- Entropy based nearest neighbor search in high dimensions
- Foundations of multidimensional and metric data structures.
- scientific article; zbMATH DE number 5506204 (Why is no real title available?)
- scientific article; zbMATH DE number 67624 (Why is no real title available?)
- scientific article; zbMATH DE number 3469437 (Why is no real title available?)
- scientific article; zbMATH DE number 2081058 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- Learning functions of \(k\) relevant variables
- Learning with errors over rings. (Abstract)
- Locality-sensitive hashing scheme based on p-stable distributions
- Multidimensional binary search trees used for associative searching
- Multiplying matrices faster than coppersmith-winograd
- New Algorithms for Learning in Presence of Errors
- Noise-tolerant learning, the parity problem, and the statistical query model
- On agnostic learning of parities, monomials, and halfspaces
- On lattices, learning with errors, random linear codes, and cryptography
- On noise-tolerant learning of sparse parities and related problems
- Point location in arrangements of hyperplanes
- Positive definite functions on spheres
- Public-key cryptosystems from the worst-case shortest vector problem
- Rectangular matrix multiplication revisited
- Similarity estimation techniques from rounding algorithms
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Cited in
(24)- A new algorithm for finding closest pair of vectors (extended abstract)
- 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
- Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- A new coding-based algorithm for finding closest pair of vectors
- Fast sketch-based recovery of correlation outliers
- A faster subquadratic algorithm for finding outlier correlations
- Detecting the large entries of a sparse covariance matrix in sub-quadratic time
- On the hardness of learning sparse parities
- scientific article; zbMATH DE number 6846423 (Why is no real title available?)
- Quickest Search and Learning Over Correlated Sequences: Theory and Application
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- On the hardness of approximate and exact (bichromatic) maximum inner product
- Properly learning decision trees in almost polynomial time
- An illuminating algorithm for the light bulb problem
- Approximating the number of relevant variables in a parity implies proper learning
- A non-trivial algorithm enumerating relevant features over finite fields
- Attribute-efficient learning of monomials over highly-correlated variables
- Counting short vector pairs by inner product and relations to the permanent
- The planted orthogonal vectors problem
- New statistical and computational results for learning junta distributions
This page was built for publication: Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796401)
