Before revision:  Our algorithm runs in time O(nnz(A) + n ^{\alpha_p}poly(k/\epsilon)), where \alpha_p = 1 for p\in [1,2) and \alpha_p = 1 + (\omega-1)(1-2/p) for p>2 and \omega \approx 2.374 is the exponent of matrix multiplication.
After revision:  Our algorithm runs in time O(nnz(A) + n ^{\alpha_p}poly(k/\epsilon)), where \alpha_p = 0 for p\in [1,2) and \alpha_p = 1 + (\omega-1)(1-2/p) for p>2 and \omega \approx 2.374 is the exponent of matrix multiplication.