{"ID":2870458,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.13112","arxiv_id":"2509.13112","title":"Sublinear-Time Algorithms for Diagonally Dominant Systems and Applications to the Friedkin-Johnsen Model","abstract":"We study sublinear-time algorithms for solving linear systems $Sz = b$, where $S$ is a diagonally dominant matrix, i.e., $|S_{ii}| \\geq δ+ \\sum_{j \\ne i} |S_{ij}|$ for all $i \\in [n]$, for some $δ\\geq 0$. We present randomized algorithms that, for any $u \\in [n]$, return an estimate $z_u$ of $z^*_u$ with additive error $\\varepsilon$ or $\\varepsilon \\lVert z^*\\rVert_\\infty$, where $z^*$ is some solution to $Sz^* = b$, and the algorithm only needs to read a small portion of the input $S$ and $b$. For example, when the additive error is $\\varepsilon$ and assuming $δ\u003e0$, we give an algorithm that runs in time $O\\left( \\frac{\\|b\\|_\\infty^2 S_{\\max}}{δ^3 \\varepsilon^2} \\log \\frac{\\| b \\|_\\infty}{δ\\varepsilon} \\right)$, where $S_{\\max} = \\max_{i \\in [n]} |S_{ii}|$. We also prove a matching lower bound, showing that the linear dependence on $S_{\\max}$ is optimal. Unlike previous sublinear-time algorithms, which apply only to symmetric diagonally dominant matrices with non-negative diagonal entries, our algorithm works for general strictly diagonally dominant matrices ($δ\u003e 0$) and a broader class of non-strictly diagonally dominant matrices $(δ= 0)$. Our approach is based on analyzing a simple probabilistic recurrence satisfied by the solution. As an application, we obtain an improved sublinear-time algorithm for opinion estimation in the Friedkin--Johnsen model.","short_abstract":"We study sublinear-time algorithms for solving linear systems $Sz = b$, where $S$ is a diagonally dominant matrix, i.e., $|S_{ii}| \\geq δ+ \\sum_{j \\ne i} |S_{ij}|$ for all $i \\in [n]$, for some $δ\\geq 0$. We present randomized algorithms that, for any $u \\in [n]$, return an estimate $z_u$ of $z^*_u$ with additive error...","url_abs":"https://arxiv.org/abs/2509.13112","url_pdf":"https://arxiv.org/pdf/2509.13112v1","authors":"[\"Weiming Feng\",\"Zelin Li\",\"Pan Peng\"]","published":"2025-09-16T14:13:31Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.LG\",\"cs.SI\"]","methods":"[]","has_code":false}