2026-07-21T12:58:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14089 2024-03-06T10:53:26Z ddc:004 open_access

Optimal Fine-Grained Hardness of Approximation of Linear Equations Bafna, Mitali Vyas, Nikhil Linear Equations Fine-Grained Complexity Hardness of Approximation The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system (A,b), for A ∈ ℝ^{n×n} and b ∈ ℝⁿ, we wish to find a vector x ∈ ℝⁿ such that Ax = b. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time O(n^ω). We consider the problem of finding ε-approximate solutions to linear systems with respect to the L₂-norm, that is, given a satisfiable linear system (A ∈ ℝ^{n×n}, b ∈ ℝⁿ), find an x ∈ ℝⁿ such that ||Ax - b||₂ ≤ ε||b||₂. Our main result is a fine-grained reduction from computing the rank of a matrix to finding ε-approximate solutions to linear systems. In particular, if the best known Õ(n^ω) time algorithm for computing the rank of n × O(n) matrices is optimal (which we conjecture is true), then finding an ε-approximate solution to a dense linear system also requires Ω̃(n^ω) time, even for ε as large as (1 - 1/poly(n)). We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices and well-conditioned linear systems. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitali Bafna and Nikhil Vyas 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.20 urn:nbn:de:0030-drops-140894 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.20 eng https://creativecommons.org/licenses/by/4.0/legalcode