Open problems

980 registered problems.

OP-00167 Open

Decidability of zero hitting by rational matrix powers

NT · decidability · linear recurrence sequences · OpenProblemsInNLA · Skolem problem

OP-00168 Open

Decidability of zero hitting by a matrix exponential

NT · continuous Skolem problem · decidability · exponential polynomials · OpenProblemsInNLA

OP-00169 Partially resolved

Optimal pivot count for RPCholesky trace approximation

NA · low-rank approximations · Nyström approximations · OpenProblemsInNLA · pivoted Cholesky factorizations

OP-00170 Partially resolved

Optimal trace-estimation complexity using Kronecker matrix-vector queries

NA · Kronecker products · OpenProblemsInNLA · query complexity · trace estimation

OP-00171 Partially resolved

Optimal query complexity of spectral rank-k approximation

NA · Krylov subspace methods · low-rank approximations · OpenProblemsInNLA · query complexity

OP-00172 Open

Query complexity from Schatten to spectral norms

NA · low-rank approximations · OpenProblemsInNLA · query complexity · Schatten norms

OP-00173 Open

Super-exponential decay of the zero-permanent probability

PR · anticoncentration · OpenProblemsInNLA · permanents · random matrices

OP-00174 Partially resolved

Minimum linear measurements for uniform recovery of real low-rank matrices

NA · determinantal varieties · linear measurements · low-rank matrix recovery · OpenProblemsInNLA

OP-00175 Partially resolved

The Goreinov–Tyrtyshnikov–Zamarashkin conjecture on square-submatrix inverse norms

NA · column subset selection · OpenProblemsInNLA · pseudoskeleton approximations

OP-00176 Open

Constant-factor HSS approximation in polynomial time

NA · approximation algorithms · hierarchical matrices · HSS matrices · OpenProblemsInNLA

OP-00177 Open

HSS approximation from a number of matvecs independent of depth

NA · HSS matrices · matrix-vector queries · OpenProblemsInNLA · sketching

OP-00178 Partially resolved

Optimal matvec query complexity of HODLR approximation

NA · HODLR matrices · matrix-vector queries · OpenProblemsInNLA · query complexity

OP-00179 Partially resolved

Sharp gap between volume sampling and the worst matrix with a prescribed spectrum

NA · column subset selection · Nyström approximations · OpenProblemsInNLA · volume sampling

OP-00180 Open

Exact bilinear rank of the 3×3 matrix product

AG · bilinear complexity · matrix multiplication · OpenProblemsInNLA · tensor rank

OP-00181 Partially resolved

Minimal asymptotic rank of the small Coppersmith–Winograd tensor

AG · asymptotic rank · Coppersmith–Winograd tensors · matrix multiplication · OpenProblemsInNLA

OP-00182 Open

Explicit tensors with quadratic border rank

AG · border rank · explicit tensors · OpenProblemsInNLA

OP-00183 Open

Scholz–Brauer inequality for multiplication chains

NT · addition chains · exponentiation · OpenProblemsInNLA

OP-00184 Open

Deterministic polynomial-time commutative Edmonds problem

NA · derandomization · OpenProblemsInNLA · polynomial identity testing · symbolic determinants

OP-00185 Partially resolved

The least positive permanent of a sign matrix

CO · OpenProblemsInNLA · permanents · sign matrices

OP-00186 Partially resolved

Realizing every sign-matrix permanent with negative entries confined on or above the diagonal

CO · OpenProblemsInNLA · permanents · sign matrices

OP-00187 Open

Deterministic near-quadratic matrix multiplication verification

NA · derandomization · matrix multiplication · OpenProblemsInNLA

OP-00188 Open

Cryer's Hadamard complete-pivoting conjecture

NA · Gaussian elimination · growth factors · Hadamard matrices · OpenProblemsInNLA

OP-00189 Open

The exact fifth complete-pivoting growth factor

NA · Gaussian elimination · growth factors · OpenProblemsInNLA

OP-00190 Partially resolved

Precision required for conjugate gradients to attain backward accuracy in n steps

NA · backward errors · conjugate gradient methods · OpenProblemsInNLA · rounding errors

OP-00191 Open

RILU conditioning for the Neumann problem on smooth planar domains

NA · condition numbers · incomplete factorizations · OpenProblemsInNLA · preconditioners

OP-00192 Open

Perturbed MILU conditioning for Neumann problems in two and three dimensions

NA · condition numbers · incomplete LU factorizations · OpenProblemsInNLA · preconditioners

OP-00193 Partially resolved

Spectral disk for a Radau stage preconditioner

NA · eigenvalue bounds · OpenProblemsInNLA · preconditioners · Runge–Kutta methods

OP-00194 Partially resolved

Positive diagonal preconditioning with a nilpotent stiff limit

NA · collocation methods · diagonal preconditioners · OpenProblemsInNLA · Runge–Kutta methods

OP-00195 Partially resolved

Exploit spectral outliers without losing input sparsity

NA · OpenProblemsInNLA · randomized algorithms · singular values · sparse linear systems

OP-00196 Partially resolved

Polynomial-time solution under the regularity promise

NA · absolute value equations · linear complementarity problems · OpenProblemsInNLA · P-matrices

OP-00197 Open

Polynomial-time deterministic restricted isometries with nearly linear row count

FA · compressed sensing · explicit constructions · OpenProblemsInNLA · restricted isometry property

OP-00198 Partially resolved

Sharp sample complexity for restricted isometries from the cyclic Fourier matrix

FA · compressed sensing · OpenProblemsInNLA · restricted isometry property · subsampled Fourier matrices

OP-00199 Partially resolved

Complex equiangular tight frames with twice the dimension

FA · conference matrices · equiangular tight frames · line packings · OpenProblemsInNLA

OP-00200 Partially resolved

The minimum number of quadratic measurements for generalized phase retrieval

FA · OpenProblemsInNLA · phase retrieval · projective spaces · quadratic measurements

OP-00201 Partially resolved

Two-vertex certification of nonsingular sign regularity

NA · interval matrices · OpenProblemsInNLA · sign regular matrices · totally nonnegative matrices

OP-00202 Open

Polynomial-time minimum-volume decision under sufficient scattering

NA · minimum-volume factorizations · nonnegative matrix factorizations · OpenProblemsInNLA · promise problems

OP-00203 Partially resolved

Exact nonnegative rank of regular polygon slack matrices

NA · extended formulations · nonnegative rank · OpenProblemsInNLA · regular polygons

OP-00204 Partially resolved

Additivity for Cartesian-product slack matrices

NA · Cartesian products · extended formulations · nonnegative rank · OpenProblemsInNLA

OP-00205 Partially resolved

Exact positive semidefinite rank of subset-intersection matrices

NA · Johnson schemes · OpenProblemsInNLA · positive semidefinite factorizations · positive semidefinite rank

OP-00206 Solution claimed

Optimal dimension for a rerandomized Hadamard embedding

NA · OpenProblemsInNLA · randomized Hadamard transforms · sketching · subspace embeddings

OP-00207 Solution claimed

Improve the worst-case approximation factor for prescribed tensor-train ranks

NA · approximation algorithms · low-rank approximations · OpenProblemsInNLA · tensor-train decompositions

OP-00208 Solution claimed

Finite mean angular condition number for identifiable tensor decomposition

NA · condition numbers · OpenProblemsInNLA · random tensors · tensor decompositions

OP-00209 Solution claimed

Sharp sparsity threshold for injectivity of a random sparse rectangular matrix

PR · OpenProblemsInNLA · smallest singular values · sparse random matrices · subspace injections

OP-00210 Lean verified

Equality of ranks for generic odd-order Hankel tensors

AG · border ranks · Hankel tensors · OpenProblemsInNLA · tensor ranks

OP-00211 Solution claimed

Comon's exact-rank conjecture for Hankel tensors

AG · Hankel tensors · OpenProblemsInNLA · symmetric tensors · tensor ranks

OP-00212 Solution claimed

Frobenius inner products minimize the algebraic complexity of rank-one approximation

AG · Euclidean distance degrees · OpenProblemsInNLA · rank-one approximations · Segre–Veronese varieties

OP-00213 Solution claimed

Rayleigh–Ritz discriminant degrees for rank-one matrices

AG · discriminants · OpenProblemsInNLA · Rayleigh quotients · Segre varieties

OP-00214 Solution claimed

A Seginer theorem for arbitrary independent identically distributed tensor entries

PR · injective norms · OpenProblemsInNLA · random tensors

OP-00215 Solution claimed

Degrees of the two Rayleigh–Ritz discriminant parts for rational normal curves

AG · discriminants · OpenProblemsInNLA · rational normal curves · Rayleigh quotients

OP-00216 Solution claimed

Border-rank deficiency forcing strict submultiplicativity at the tensor square

AG · border ranks · OpenProblemsInNLA · secant varieties · tensor products