Linear Systems and Eigenvalue Problems — Problem 7

Definitions and mathematical statement

A linear system is written schematically as \[ Ax=b, \] where $A$ is the coefficient matrix, $b$ is the right-hand side, and $x$ is the unknown vector. The supplied record does not specify the scalar domain, matrix dimensions, or admissible inputs.

The source question is: determine the computational complexity of solving linear systems described by the parameter tuple \[ (n,0,l,\kappa), \] and determine how that complexity depends on whether the computation uses direct access or matrix--vector products.

Unresolved formulation. The supplied record does not define this parameterized class or the meanings and admissible ranges of $n$, $l$, and $\kappa$. It also does not explain the significance of the second coordinate $0$. In particular, no interpretation of $\kappa$ as a specific condition number is stipulated here. The permitted access operations, their costs, the representation of the input and output, the meaning of solving, and any accuracy or success-probability requirement are unspecified. Thus the displayed tuple and the comparison of the two named models are retained as the source question; a precise complexity problem requires the missing definitions.

Short English statement

Determine the complexity of solving the source's $(n,0,l,\kappa)$ linear systems, comparing direct access with matrix--vector product access. The parameter meanings, input class, solution requirements, and computational costs are absent from the supplied record, so the formulation remains incomplete.

Sources

• Local UnsolvedMath registry: supplied complete record with permanent ID $800498$, source problem code catalogue entry, titled Linear Systems and Eigenvalue Problems --- Problem 7. The record 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 or literature assessment.
• Supplied source attribution: Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 7. Supplied URL: https://arxiv.org/abs/2602.05394. The record reports access on 2026-10-16 and extraction by arxiv_latex; these provenance claims have not been independently verified here. The referenced document's definitions and surrounding discussion are not included in the supplied evidence.