Optimal fine-grained hardness of approximation of linear equations
From MaRDI portal
Cites work
- A generalization of the fast LUP matrix decomposition algorithm and applications
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
- Deterministic reduction of integer nonsingular linear system solving to matrix multiplication
- Deterministic unimodularity certification
- Distributed PCP theorems for hardness of approximation in P
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Eigenvalues and Condition Numbers of Random Matrices
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fast matrix rank algorithms and applications
- Fast sparse matrix multiplication
- Faster inversion and other black box matrix computations using efficient block projections
- Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
- Gaussian elimination is not optimal
- Hardness results for structured linear systems
- scientific article; zbMATH DE number 3698383 (Why is no real title available?)
- scientific article; zbMATH DE number 177858 (Why is no real title available?)
- scientific article; zbMATH DE number 7788369 (Why is no real title available?)
- Matrix multiplication via arithmetic progressions
- Maximum matchings in planar graphs via Gaussian elimination
- Methods of conjugate gradients for solving linear systems
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
- On solving linear systems in sublinear time
- On some fine-grained questions in algorithms and complexity
- On the parameterized complexity of approximating dominating set
- Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard
- Powers of tensors and fast matrix multiplication
- Probabilistic polynomials and Hamming nearest neighbors
- Proof verification and the hardness of approximation problems
- Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations
- Solving sparse linear equations over finite fields
- Some optimal inapproximability results
- Sparsified Cholesky and multigrid solvers for connection Laplacians
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- The complexity of partial derivatives
- The shifted number system for fast linear algebra on integer matrices
- Triangular Factorization and Inversion by Fast Matrix Multiplication
This page was built for publication: Optimal fine-grained hardness of approximation of linear equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241116)
