A new coding-based algorithm for finding closest pair of vectors

DOI10.1016/J.TCS.2019.03.011MaRDI QIDQ2420648zbMATH OpenOpenAlexFDO

Authors Ning Xie, Shuai Xu, Yekun Xu

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.03.011

zbMATH Keywords

error-correcting codesclosest pair problemlight bulb problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Theory of error-correcting codes and error-detecting codes (94B99)

Recommendations

• A new algorithm for finding closest pair of vectors (extended abstract)
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• The Closest Pair Problem under the Hamming Metric
• On finding the closest bitwise matches in a fixed set
• A Faster Subquadratic Algorithm for Finding Outlier Correlations

Cites work

• scientific article; zbMATH DE number 3133919 (Why is no real title available?)
• scientific article; zbMATH DE number 5506204 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 1284436 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 1775451 (Why is no real title available?)
• scientific article; zbMATH DE number 6846423 (Why is no real title available?)
• scientific article; zbMATH DE number 1424308 (Why is no real title available?)
• A Faster Subquadratic Algorithm for Finding Outlier Correlations
• A Randomized Algorithm for Closest-Point Queries
• A simple randomized sieve algorithm for the closest-pair problem
• Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• Faster all-pairs shortest paths via circuit complexity
• Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
• Locality-sensitive hashing scheme based on \(p\)-stable distributions
• Mean, Median and Mode in Binomial Distributions
• More applications of the polynomial method to algorithm design
• Multidimensional divide-and-conquer
• Multiplying matrices faster than coppersmith-winograd
• On computing nearest neighbors with applications to decoding of binary linear codes
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
• Optimal hashing-based time-space trade-offs for approximate near neighbors
• Point location in arrangements of hyperplanes
• The light bulb problem
• The polynomial method in circuit complexity applied to algorithm design (invited talk)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(3)

• A new algorithm for finding closest pair of vectors (extended abstract)
• An illuminating algorithm for the light bulb problem
• The Closest Pair Problem under the Hamming Metric

This page was built for publication: A new coding-based algorithm for finding closest pair of vectors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420648)