2026-07-23T03:21:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20150 2024-07-02T07:52:48Z ddc:004 open_access

Finer-Grained Reductions in Fine-Grained Hardness of Approximation Abboud, Elie Ron-Zewi, Noga Fine-grained complexity conditional lower bound fine-grained reduction Approximation algorithms Analysis of algorithms Computational geometry Computational and structural complexity theory We investigate the relation between δ and ε required for obtaining a (1+δ)-approximation in time N^{2-ε} 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 N^{2-ε}, then there is no (1+δ)-approximation algorithm for (bichromatic) Euclidean Closest Pair running in time N^{2-2ε}, where δ ≈ (ε/c)² (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)⁶. Our result implies in turn that no (1+δ)-approximation algorithm exists for Euclidean closest pair for δ ≈ ε⁴, unless an algorithmic improvement for IP is obtained. This in turn is very close to the approximation guarantee of δ ≈ ε³ 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elie Abboud and Noga Ron-Zewi 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.7 urn:nbn:de:0030-drops-201507 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode