2023/11/01 by Abboud, Elie, Ron-Zewi, Noga
#Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.00798
We investigate the relation between δ and ε required for obtaining a (1+δ)-approximation in time N2-ε for closest pair problems under various distance metrics, and for other related problems in fine-grained complexity. Specifically, our main result shows that if it is impossible to (exactly) solve the (bichromatic) inner product (IP) problem for vectors of dimension c log N in time N2-ε, then there is no (1+δ)-approximation algorithm for (bichromatic) Euclidean Closest Pair running in time N2-2ε, where δ≈ (ε/c)2 (where ≈ hides \polylog factors). This improves on the prior result due to Chen and Williams (SODA 2019) which gave a smaller polynomial dependence of δ on ε, on the order of δ≈ (ε/c)6. Our result implies in turn that no (1+δ)-approximation algorithm exists for Euclidean closest pair for δ≈ ε4, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of δ≈ ε3 for Euclidean closest pair, given by the best known algorithm of Almam, Chan, and Williams (FOCS 2016). By known reductions, a similar result follows for a host of other related problems in fine-grained hardness of approximation. Our reduction combines the hardness of approximation framework of Chen and Williams, together with an MA communication protocol for IP over a small alphabet, that is inspired by the MA protocol of Chen (Theory of Computing, 2020).