Summary
The paper studies the (approximate) estimation of effective resistance on expander graphs, i.e., graphs with edge expansion $\Omega(1/\text{polylog}\ n)$. The main upper-bound result is a data structure (sketch) for effective resistance that takes $\tilde{O}(m/\epsilon)$ time to build, answers each query in $\tilde{O}(1)$ time, and is of size $\tilde{O}(m/\epsilon)$. This improves the Li and Sachdeva [SODA’23] on the construction time on sparse expanders with $O(n/\epsilon)$ edges. The data structure implies an $\tilde{O}(n^2/\epsilon)$-time algorithm to compute all-pairs effective resistance. To complement the upper bound result, the paper further includes a lower bound of $\tilde{\Omega}(n^2/\epsilon^{0.5})$ time for computing all-pairs effective resistance for all algorithms that are not based on fast matrix multiplications (FMM).
The main technical ingredient for the upper bound result is to use asymmetric factorization of the effective resistance in expander graphs (in the form of $\ell_{1}$ norm) and apply the count-sketch in $\ell_{1}$ to achieve the $\epsilon^{-1}$ compression. For the lower bound side, the paper designs a novel reduction to the triangle detection problem, which improves the exponent on $\epsilon$ from $1/13$ to $1/2$.
My general evaluation of the paper is positive. The paper seems to require a good deal of background to read, and I did not manage to check the correctness of the proofs. The high-level intuitions make sense to me, and conditioning on equation (2) is correct, I think everything goes through for the upper bound. As such, as far as I can see, the paper is technically solid, and it makes progress toward an interesting open problem. On the flip side, it seems the improvements of this paper are rather restrictive – compared to Li and Sachdeva [SODA’23], it is only better on expander with $O(n/\epsilon)$ edges. For the presentations, I think the paper generally makes good efforts to define notions and explain ideas clearly. However, I still believe that the writing assumes a very strong level of knowledge from the reader (see the weakness part for details).
Strengths
As I have mentioned in the general evaluation, I think the paper is technically solid, and the presentation is clear in general. The high-level intuitions provided in the paper are helpful to the readers, and the techniques include novel ideas of the symmetric factorization of the effective resistance.
Weaknesses
Most of them are already mentioned in the general evaluation. Here is a list that would help the authors to address:
- On the upper bound side, the improvement compared to Li and Sachdeva [SODA’23] is rather limited – the bound is only better on expanders with $O(n/\epsilon)$ edges.
- As I said in the general evaluation, the paper seems to require a good deal of background to read. I realize that the authors have already put efforts into making the paper more accessible by defining most of the notions clearly from the get-go and presenting the high-level ideas concisely. However, in my (very subjective) opinion, reading the paper still requires some non-trivial efforts.
- I think some of the presentation problems can be attributed to unclear notations, for instance:
1. $\tilde{O}(\cdot)$ is defined after multiple usages in section 1, and $\tilde{\Omega}(\cdot)$ is never defined. This is especially confusing since I think you hide $\text{polylog}$ vs. $1/\text{polylog}$ factors in the two notations.
2. The edge-vertex incident matrix $B_{G}$ is briefly mentioned but never formally defined (I know that it is): this could be an issue for the general audience at NeurIPS to understand.
3. Is $J$ in line 194 the matrix for the JL projection? It is never mentioned.
- Finally, for NeurIPS, it would be good if you could spend more passage talking about downstream applications and what your bound would imply therein.
Questions
Most of them are presentation-related issues, and some of them are comments
- Line 63, do you mean $(\tilde{O}(m \epsilon^{-1}), \tilde{O}(1), \tilde{O}(n \epsilon^{-1}))$? (The current notation means sublinear time but linear size.)
- Similarly, the order seems to be wrong in line 187 – should be $(\tilde{O}(m \epsilon^{-2}), \tilde{O}(\epsilon^{-2}), \tilde{O}(n \epsilon^{-2}))$ according to your notation.
- Line 120: ‘Building on this work’ – what do you mean? Based on this manuscript?
- Line 198: there are two ‘vectors’.
- Formatting issue: For some reason, most of your citations do not contain the venue of publication; some of them have the venue but not the title – please fix this.
- Minor formatting issue: adding *actual citations* in the abstract seems to be non-standard, i.e., I think it is ok to write as (Chu et al. [Arxiv’18]), but not putting the actual pointer there.
- Did you state the (conditional) hardness result for triangle detection anywhere in the paper? I would recommend including it in the preliminary.
- I do not quite understand the logic of ruling out FFM-based algorithms: from the statement of theorem 3, it seems the reduction between effective resistance and triangle detection is unconditional. So why the reduction does not work for FFM-based algorithms? Is it because of the hardness result of triangle detection?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
I do not see any immediate non-technical/societal limitations on the work. Presentation-wise, it would be good if the paper had discussed more downstream applications.