Finer-Grained Hardness of Kernel Density Estimation

Josh Alman, Yunfeng Guan

In batch Kernel Density Estimation (KDE) for a kernel function $f$, we are given as input $2n$ points $x^{(1)},\cdots ,x^{(n)},y^{(1)},\cdots ,y^{(n)}$ in dimension $m$, as well…