Towards Optimal Effective Resistance Estimation
Authors: Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide new algorithms and conditional hardness for the problem of estimating effective resistances in n-node m-edge undirected, expander graphs. Both our algorithms and lower bounds develop more general tools for handling related problems for more general (not-necessarily Laplacian) matrices. |
| Researcher Affiliation | Academia | Rajat Vadiraj Dwaraknath Stanford University rajatvd@stanford.edu Ishani Karmarkar Stanford University ishanik@stanford.edu Aaron Sidford Stanford University sidford@stanford.edu |
| Pseudocode | Yes | Because the ~δi,j queries appearing in effective resistance computations are 2-sparse and p2, DMqnumerically sparse for all SDD matrices M, taking M LG in Theorem 7 immediately implies Theorem 2 and Theorem 3 (see supplementary material for detailed discussion and pseudocode.) |
| Open Source Code | No | The paper describes algorithms and theoretical results, but does not state that source code for the methodology is openly available or provide a link. |
| Open Datasets | No | This is a theoretical paper focused on algorithms and lower bounds; it does not utilize datasets for empirical training or evaluation. |
| Dataset Splits | No | This is a theoretical paper; it does not involve dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper and does not describe hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not list specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper focused on algorithms and lower bounds, and as such, it does not include details on experimental setup or hyperparameters. |