Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
A New Approach to Laplacian Solvers and Flow Problems
Authors: Patrick Rebeschini, Sekhar Tatikonda
JMLR 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper investigates the behavior of the Min-Sum message passing scheme to solve systems of linear equations in the Laplacian matrices of graphs and to compute electric flows. ... In this paper we establish a framework to analyze Min-Sum to solve voltage and flow problems. We characterize the error committed by the algorithm on general weighted graphs in terms of hitting times of random walks ... The framework that we introduce extends the analysis of Min Sum to settings where the contraction arguments previously considered in the literature ... can not be used, possibly in the presence of constraints. ... Here we present numerical results for a few classes of d-regular graphs (for convenience of presentation, we include also the numerical results related to the quantities eγ(t) and eγave(t) that control the convergence behavior of the Min-Sum algorithm in the flow problem and that will be defined later on in Section 4.3). |
| Researcher Affiliation | Academia | Patrick Rebeschini EMAIL Department of Statistics University of Oxford Oxford, OX1 3LB, UK Sekhar Tatikonda EMAIL Department of Statistics and Data Science Yale University New Haven, CT 06511, USA |
| Pseudocode | Yes | Algorithm 1: Min-Sum Algorithm 2: Min-Sum, voltage problem Algorithm 3: Min-Sum, voltage problem, quadratic messages Algorithm 4: Min-Sum, flow problem Algorithm 5: Min-Sum, flow problem, quadratic messages, no leaves |
| Open Source Code | No | The paper does not contain any statements or links indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper focuses on theoretical analysis of algorithms for graph problems (Laplacian solvers, flow problems) on abstract graph structures (general weighted graphs, d-regular graphs, complete graphs, cycles, tori). It does not mention using any specific named datasets for empirical evaluation or provide access information for any dataset. |
| Dataset Splits | No | The paper does not use any specific datasets for empirical evaluation, therefore, it does not provide information about training/test/validation dataset splits. |
| Hardware Specification | No | The paper does not provide any specific details about the hardware used to run simulations or calculations for the numerical results presented. General computing resources are not mentioned, nor are specific GPU/CPU models. |
| Software Dependencies | No | The paper does not mention any specific software dependencies or their version numbers that would be needed to reproduce the work. It describes algorithms theoretically and presents numerical results for derived quantities, but does not specify implementation details like programming languages, libraries, or solvers with version numbers. |
| Experiment Setup | No | The paper focuses on the theoretical analysis and convergence properties of the Min-Sum algorithm. While it includes 'numerical results' (e.g., plots of γ(t) decay), these are illustrative of theoretical bounds rather than outcomes of experiments with specific training configurations, hyperparameters, or system-level settings for a practical application of the algorithm. Therefore, details about an experimental setup are not provided. |