Linear Systems and Eigenvalue Problems — Problem 9

Definitions and mathematical statement

The supplied source refers to a class of linear systems called $(n,k,l,\kappa)$ systems, but the supplied record does not define this class or the meanings and admissible ranges of its parameters. Retaining this unresolved terminology, the question is:

Determine the bit complexity of solving $(n,k,l,\kappa)$ linear systems. In particular, does the running-time bound stated in the source for $(n,k,0,\kappa)$ systems, \[ \widetilde O\!\left(k^\omega+n^2\kappa\right), \] extend to the Word-RAM model?

A fully specified mathematical formulation requires the definition of the system class, the coefficient domain, the input encoding, the required output and its accuracy, and the computational assumptions. The supplied record also does not specify the meaning of $\omega$, the factors suppressed by $\widetilde O$, the model underlying the displayed bound, or the Word-RAM word length and permitted operations. The displayed bound is retained as a source assertion; its hypotheses and validity are not independently established here.

Short English statement

Determine the bit complexity of solving the source's $(n,k,l,\kappa)$ linear systems, and whether its stated $\widetilde O(k^\omega+n^2\kappa)$ bound for the case $l=0$ also holds in the Word-RAM model. The system class and computational specifications are missing from the supplied record, so this remains a qualified statement-only draft.

Sources

• Local UnsolvedMath registry: supplied complete source record, permanent ID $800500$, exact source problem code catalogue entry, title "Linear Systems and Eigenvalue Problems — Problem 9." The registry attributes the problem to Amsel, Baumann et al., with proposed year 2026, and labels it open; this label is supplied curation, not an independently verified mathematical assessment.
• Supplied source attribution: Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 9. Supplied URL: https://arxiv.org/abs/2602.05394. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance notes, not a claim of independent source access or verification.