Finer-grained Reductions in Fine-grained Hardness of Approximation

Elie Abboud, Noga Ron-Zewi

We investigate the relation between $\delta$ and $\epsilon$ required for obtaining a $(1+\delta )$-approximation in time $N^{2-\epsilon }$ for closest pair problems under various distance metrics, and for o…