Linear Systems and Eigenvalue Problems — Problem 10

Definitions and mathematical statement

Write the linear system as \[ Ax=b,\qquad A=(a_{ij})_{1\leq i,j\leq n}, \] where $b$ is a compatible right-hand side, and define \[ \operatorname{nnz}(A)=\left|\{(i,j):a_{ij}\neq 0\}\right|. \] The supplied record does not specify the coefficient domain or its representation.

Problem (supplied source, Problem 10). Determine the bit complexity of solving an $n\times n$ linear system in terms of $n$, $\operatorname{nnz}(A)$, and the necessary input and output representation parameters. In particular, does the runtime bound \[ \widetilde O\!\left(n\,\operatorname{nnz}(A)\right) \] extend to the Word-RAM model?

Here bit complexity counts elementary bit operations. In a Word-RAM model, data are stored in words and specified operations on words have unit cost. The word length and permitted operations must be specified to make the latter question precise. The notation $\widetilde O$ indicates suppression of polylogarithmic factors, but the source record does not identify the parameters in those factors.

Unresolved qualifications. The record does not specify coefficient encodings or bit lengths, assumptions on $A$, the treatment of inconsistent or nonunique systems, whether a solution must be exact or approximate, or the permitted use and success guarantees of randomization. It also does not identify the computational model and hypotheses of the referenced runtime bound. Thus the displayed question preserves the source target but does not specify a single fully quantified complexity conjecture.

Short English statement

For a linear system with $n$ equations and $\operatorname{nnz}(A)$ nonzero matrix entries, determine the cost of finding a solution using bit operations, and ask whether a $\widetilde O(n\operatorname{nnz}(A))$ runtime is available in the Word-RAM model. The coefficient representation, solution requirements, and computational assumptions remain unspecified.

Sources

• Local UnsolvedMath registry, permanent ID $800501$, exact source problem code catalogue entry; title: Linear Systems and Eigenvalue Problems --- Problem 10. The registry attributes the problem to Amsel, Baumann et al. (2026) and labels it open; this is supplied status metadata, not an independently verified assessment.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 10. Supplied source URL: https://arxiv.org/abs/2602.05394. The supplied provenance records access on 2026-10-16 and extraction by arxiv_latex; neither source access nor the extracted statement has been independently verified here.