Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors propose fast algorithms for exact matrix-vector computations when the matrices are pairwise distance matrices (not strictly metrics). This leads to fast algorithms for matrix multiplication when one factor is a distance matrix.

They also give hopeless lower bounds for the $\ell_\infty$ distance, but fast approximate algorithms.

A third contribution is relegated to the appendix.

They present a small set of experiments to showcase the practical advantages of one of their algorithms.

strengths_and_weaknesses: The paper is very well written and easy to follow. All the arguments in the main body seem sound to me.

One possible objection is the substance of the algorithms for $\ell_p$ distances, in particular $\ell_1$, which could almost be considered low-hanging fruit. The case of $\ell_\infty$ is much more inspired, and the reduction of OVP, while not very difficult, is non-trivial.

Minor: In the discussion of the binary case in section 3.1, t seems to come out of nowhere.

Some typos I ran into:
  - Theorem 1.1. z should be in R^n.
  - l. 162: "The sampling probabilities only needs"
  - l. 166: "T is the time requires to perform a matrix-vector query."
  - l. 271: "This motives"

questions: I'm a bit surprised that no one had come up with the algorithm for $\ell_1$ before. Could you perhaps comment on that?
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This submission discusses 3 main results which the authors explicitly state on page 2 and again on pages 2 and 3.  Viz, for a distance matrix A of n points in d-dim Euclidean distance

o Computation of A.z in O(ndp)+ O(nd log(n)) steps for l_p norm 1<=p<inf
o Computation of A.B in O(n^2dp) steps for l_p norm 1<=p<=inf
o Computation of distance matrix A itself for n points in R^d in time O(n^2 log(n))
strengths_and_weaknesses: 
This submission is effectively a long journal paper on numerical linear algebra divided in an ad hoc way to fit into the NeurIPS template.  The three results presented are significant and the proof methodology is intricate.  Efficacy of the results are well demonstrated by the experiments.

On the negative side, this paper has less relevance to ML and much more relevance to numerical linear algebra: its only claim for relevance to ML is that distance matrices arise in ML often as do need for the stated 3 results.  In this reviewer's opinion, this submission should be written in a linear way *not* separating material in the supplements from the main text (to meet NeurIPS page limit as in current form) thus presenting the material in a logical way in 30 or so pages and be submitted it to a numerical algebra publication (such as SIAM Journal in Numerical Algebra) where seasoned numerical analysts who only do matrix algebra will be able to provide much more valuable feedback to the authors.
questions: 
I found Section B in the supplement to be fundamental to the rationale for writing this paper and its separation from the main text is incomprehensible except for the NeurIPS page limit, excluding supplementary material.
limitations: NA.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The matrix-vector multiplication problem is fundamental and super important in ML applications. Faster algorithms for it are highly desirable.

This paper presents major speedups for the problem under the assumption that the matrix is not worst-case but is actually a "distance matrix" meaning that there is a set of n points x_1,...,x_n that implicitly define the matrix: the i,j entry is the distance between x_i and x_j.

This setting seems well-motivated and natural.

The complexity of this problem varies with the specific distance metric that is used, and with the dimension of the data-points x_1,..,x_n. 

For \ell_1 distance over d dimensional points, the paper presents and algorithm computing the matrix-vector product in O(nd) time rather than the naive O(n^2) worst case bound. Technically, this algorithm is pretty simple and is at the level of an exercise. 

There are other efficient algorithms for other norms that are not presented in the body of the paper.

For \ell_infinity over d=O(log n) dimensions, the paper shows a conditional lower bound stating that n^2 time is required, and then they present some interesting approximation algorithms. Both upper and lower bounds in this context are non-trivial but they use rather standard techniques in the context of nearest neighbor algorithms for such metrics.
strengths_and_weaknesses: The results of this paper are super important and interesting, to a point that I would be surprised if they are actually new. But since I can't point to a previous reference that proves these results, I recommend accepting the paper.

The main weakness is that the techniques are not so groundbreaking; still, they are nontrivial observations that yield great results.
questions: Are you aware of this paper? Isn't there some overlap in results/techniques:

"Algorithms and Hardness for Linear Algebra on Geometric Graphs"
Josh Alman; Timothy Chu; Aaron Schild; Zhao Song

limitations: N/A
review_title: null

Meta-review: metareview: The authors propose fast algorithms for exact matrix-vector computations when the matrices are pairwise distance matrices (not strictly metrics). This leads to fast algorithms for matrix multiplication when one factor is a distance matrix. Experimental results are included, as well as lower and upper bounds.

As the reviewers wrote, the paper is very well written and easy to follow. All the arguments in the main body seem sound.

I agree with the authors that this is a fundamental problem in machine learning with many modern applications.
Please consider adding some text from Section B as suggested by one of the reviewer.
confidence: Certain
Decision: Accept