Fetching the paper…
Reading the bibliography…
Every graph $G$ can be represented by a collection of equi-radii spheres in a $d$-dimensional metric $\Delta$ such that there is an edge $uv$ in $G$ if and only if the spheres corresponding to $u$ and $v$ intersect.
On the boxicity and cubicity of a graph
Fred S Roberts · 1969
Earlier work this paper cites.
Class of constructive asymptotically good algebraic codes
Jørn Justesen · 1972
Earlier work this paper cites.
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.
Probabilistic algorithms
Michael O. Rabin · 1976
Earlier work this paper cites.
Multidimensional divide-and-conquer
Jon Louis Bentley · 1980
Earlier work this paper cites.
Lower bounds for algebraic computation trees (preliminary report)
Michael Ben-Or · 1983
Earlier work this paper cites.
An olla-podrida of open problems, often oddly posed
Richard K Guy · 1983
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
William B Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
Space graphs and sphericity
Hiroshi Maehara · 1984
Earlier work this paper cites.
Contact patterns of equal nonoverlapping spheres
Hiroshi Maehara · 1985
Earlier work this paper cites.
On the contact dimensions of graphs
Peter Frankl and Hiroshi Maehara · 1988
Earlier work this paper cites.
Plane-sweep solves the closest pair problem elegantly
Klaus H. Hinrichs, Jürg Nievergelt, and Peter Schorn · 1988
Cited alongside, same era.
Dispersed points and geometric embedding of complete bipartite graphs
Hiroshi Maehara · 1991
Cited alongside, same era.
Lower bounds for algebraic computation trees with integer inputs
Andrew Chi-Chih Yao · 1991
Cited alongside, same era.
A few applications of negative- type inequalities
Michel Deza and Hiroshi Maehara · 1994
Cited alongside, same era.
A simple randomized sieve algorithm for the closest-pair problem
Samir Khuller and Yossi Matias · 1995
Cited alongside, same era.
Embedding into rectilinear spaces
Hans-Jürgen Bandelt, Victor Chepoi, and Monique Laurent · 1998
Cited alongside, same era.
Computational Complexity: A Conceptual Perspective
Oded Goldreich · 2008
Later among the works it cites.
Introduction to the non-asymptotic analysis of random matrices
Roman Vershynin · 2010
Later among the works it cites.
Probabilistic polynomials and hamming nearest neighbors
Josh Alman and Ryan Williams · 2015
Later among the works it cites.
Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk)
Virginia Vassilevska Williams · 2015
Later among the works it cites.
Fine-grained algorithms and complexity (invited talk)
Virginia Vassilevska Williams · 2016
Closest in time.
Distributed PCP theorems for hardness of approximation in P
Amir Abboud, Aviad Rubinstein, and R. Ryan Williams · 2017
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Equilateral dimension of the rectilinear space
Jack H. Koolen, Monique Laurent, and Alexander Schrijver · 2000
Cited alongside, same era.
Equilateral sets in ℓ p n \ell_{p}^{n}
Noga Alon and Pavel Pudlák · 2003
Cited alongside, same era.
Closest pair problems in very high dimensions
Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, and Ely Porat · 2004
Cited alongside, same era.
Monotone maps, sphericity and bounded second eigenvalue
Yonatan Bilu and Nathan Linial · 2005
Cited alongside, same era.
A new algorithm for optimal 2-constraint satisfaction and its implications
Ryan Williams · 2005
Cited alongside, same era.
Closest in time.
Distributed PCP theorems for hardness of approximation in P
Amir Abboud, Aviad Rubinstein, and Ryan Williams · 2017
Closest in time.
Dominance product and high-dimensional closest pair under L ∞ {L}_{\infty}
Omer Gold and Micha Sharir · 2017
Closest in time.
Hardness of approximate nearest neighbor search
Aviad Rubinstein · 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.
On some fine-grained questions in algorithms and complexity
Virginia Vassilevska Williams · 2018
Closest in time.