Fetching the paper…
Reading the bibliography…
We prove conditional near-quadratic running time lower bounds for approximate Bichromatic Closest Pair with Euclidean, Manhattan, Hamming, or edit distance.
Closest-point problems
Michael Ian Shamos and Dan Hoey · 1975
Earlier work this paper cites.
Divide-and-conquer in multidimensional space
Jon Louis Bentley and Michael Ian Shamos · 1976
Earlier work this paper cites.
Codes on algebraic curves
Valerii Denisovich Goppa · 1981
Earlier work this paper cites.
Scaling and related techniques for geometry problems
Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan · 1984
Earlier work this paper cites.
Euclidean minimum spanning trees and bichromatic closest pairs
Pankaj K. Agarwal, Herbert Edelsbrunner, and Otfried Schwarzkopf · 1991
Earlier work this paper cites.
Private vs. common random bits in communication complexity
Ilan Newman · 1991
Earlier work this paper cites.
Approximate nearest neighbor queries in fixed dimensions
Sunil Arya and David M. Mount · 1993
Earlier work this paper cites.
An optimal algorithm for approximate nearest neighbor searching
Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu · 1994
Earlier work this paper cites.
A simple randomized sieve algorithm for the closest-pair problem
Samir Khuller and Yossi Matias · 1995
Earlier work this paper cites.
Two algorithms for nearest-neighbor search in high dimensions
Jon M. Kleinberg · 1997
Earlier work this paper cites.
Proof verification and the hardness of approximation problems
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy · 1998
Earlier work this paper cites.
Probabilistic checking of proofs: A new characterization of NP
Sanjeev Arora and Shmuel Safra · 1998
Earlier work this paper cites.
Approximate nearest neighbors: towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
Improved decoding of reed-solomon and algebraic-geometry codes
Venkatesan Guruswami and Madhu Sudan · 1999
Earlier work this paper cites.
A sublinear time approximation scheme for clustering in metric spaces
Piotr Indyk · 1999
Earlier work this paper cites.
Dimensionality reduction techniques for proximity problems
Piotr Indyk · 2000
Earlier work this paper cites.
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani · 2000
Earlier work this paper cites.
On the complexity of k-sat
Russell Impagliazzo and Ramamohan Paturi · 2001
Earlier work this paper cites.
A low-complexity algorithm for the construction of algebraic-geometric codes better than the gilbert-varshamov bound
Kenneth W. Shum, Ilia Aleshnikov, P. Vijay Kumar, Henning Stichtenoth, and Vinay Deolalikar · 2001
Earlier work this paper cites.
Lower bounds for embedding edit distance into normed spaces
Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, and Sofya Raskhodnikova · 2003
Earlier work this paper cites.
Expected-case complexity of approximate nearest neighbor searching
Sunil Arya and Ho-Yam Addy Fu · 2003
Earlier work this paper cites.
Better algorithms for high-dimensional proximity problems via asymmetric embeddings
Piotr Indyk · 2003
Earlier work this paper cites.
Rectangle size bounds and threshold covers in communication complexity
Hartmut Klauck · 2003
Earlier work this paper cites.
Approximating edit distance efficiently
Ziv Bar-Yossef, TS Jayram, Robert Krauthgamer, and Ravi Kumar · 2004
Earlier work this paper cites.
Approximate nearest neighbor under edit distance via product metrics
Piotr Indyk · 2004
Earlier work this paper cites.
Nonembeddability theorems via fourier analysis
Subhash Khot and Assaf Naor · 2005
Earlier work this paper cites.
A new algorithm for optimal 2 2 -constraint satisfaction and its implications
R. Ryan Williams · 2005
Earlier work this paper cites.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Alexandr Andoni and Piotr Indyk · 2006
Cited alongside, same era.
On the optimality of the dimensionality reduction method
Alexandr Andoni, Piotr Indyk, and Mihai Patrascu · 2006
Cited alongside, same era.
Oblivious string embeddings and edit distance approximations
Tuğkan Batu, Funda Ergun, and Cenk Sahinalp · 2006
Cited alongside, same era.
The computational hardness of estimating edit distance [extended abstract]
Alexandr Andoni and Robert Krauthgamer · 2007
Cited alongside, same era.
The PCP theorem by gap amplification
Irit Dinur · 2007
Cited alongside, same era.
Lower bounds on locality sensitive hashing
Rajeev Motwani, Assaf Naor, and Rina Panigrahy · 2007
Cited alongside, same era.
Beyond locality-sensitive hashing
Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn · 2014
Later among the works it cites.
Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets
Venkatesan Guruswami and Chaoping Xing · 2014
Later among the works it cites.
Optimal lower bounds for locality-sensitive hashing (except when q is tiny)
Ryan O’Donnell, Yi Wu, and Yuan Zhou · 2014
Later among the works it cites.
Tight hardness results for LCS and other sequence similarity measures
Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams · 2015
Later among the works it cites.
Practical and optimal lsh for angular distance
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt · 2015
Later among the works it cites.
Optimal data-dependent hashing for approximate near neighbors
Alexandr Andoni and Ilya Razenshteyn · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Low distortion embeddings for edit distance
Rafail Ostrovsky and Yuval Rabani · 2007
Cited alongside, same era.
Randomization does not help searching predecessors
Mihai Patrascu and Mikkel Thorup · 2007
Cited alongside, same era.
Hardness of nearest neighbor under l-infinity
Alexandr Andoni, Dorian Croitoru, and Mihai Patrascu · 2008
Cited alongside, same era.
Correlated algebraic-geometric codes: Improved list decoding over bounded alphabets
Venkatesan Guruswami and Anindya C. Patthak · 2008
Cited alongside, same era.
A geometric approach to lower bounds for approximate near-neighbor search and partial match
Rina Panigrahy, Kunal Talwar, and Udi Wieder · 2008
Cited alongside, same era.
Space-time tradeoffs for approximate nearest neighbor searching
Sunil Arya, Theocharis Malamatos, and David M. Mount · 2009
Cited alongside, same era.
Later among the works it cites.
A directed isoperimetric inequality with application to bregman near neighbor lower bounds
Amirali Abdullah and Suresh Venkatasubramanian · 2015
Later among the works it cites.
Probabilistic polynomials and hamming nearest neighbors
Josh Alman and Ryan Williams · 2015
Later among the works it cites.
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
Arturs Backurs and Piotr Indyk · 2015
Later among the works it cites.
Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
Gregory Valiant · 2015
Later among the works it cites.
Polynomial representations of threshold functions and algorithmic applications
Josh Alman, Timothy M. Chan, and R. Ryan Williams · 2016
Later among the works it cites.
Constant rate pcps for circuit-sat with sublinear query complexity
Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, and Henning Stichtenoth · 2016
Later among the works it cites.
The curse of medium dimension for geometric problems in almost every norm
Roee David, Karthik C. S., and Bundit Laekhanukit · 2016
Later among the works it cites.
A faster subquadratic algorithm for finding outlier correlations
Matti Karppa, Petteri Kaski, and Jukka Kohonen · 2016
Later among the works it cites.
Randomized approximate nearest neighbor search with limited adaptivity
Mingmou Liu, Xiaoyin Pan, and Yitong Yin · 2016
Later among the works it cites.
Optimal las vegas locality sensitive data structures
Thomas Dybdahl Ahle · 2017
Later among the works it cites.
Optimal hashing-based time-space trade-offs for approximate near neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and Erik Waingarten · 2017
Later among the works it cites.
Distributed PCP theorems for hardness of approximation in P
Amir Abboud, Aviad Rubinstein, and R. Ryan Williams · 2017
Later among the works it cites.
Interactive oracle proofs with constant rate and query complexity
Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner · 2017
Later among the works it cites.
Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
Timothy M. Chan · 2017
Later among the works it cites.
Local list recovery of high-rate tensor codes and applications
Brett Hemenway, Noga Ron-Zewi, and Mary Wootters · 2017
Later among the works it cites.
High-Dimensional Similarity Search and Sketching: Algorithms and Hardness
Ilya Razenshteyn · 2017
Later among the works it cites.
Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
Amir Abboud and Aviad Rubinstein · 2018
Closest in time.
On the hardness of approximate and exact (bichromatic) maximum inner product
Lijie Chen · 2018
Closest in time.
On the parameterized complexity of approximating dominating set
Karthik C.S., Bundit Laekhanukit, and Pasin Manurangsi · 2018
Closest in time.
On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity
Ryan Williams · 2018
Closest in time.