Open problems

1131 registered problems.

OP-00051 Solution claimed

The Group Spencer conjecture

CO · discrepancy theory · Matrix Spencer · Randomstrasse101 · regular representation

OP-00052 Solution claimed

Global synchronization with negative edges

PR · Burer–Monteiro · community detection · global synchronization · Kuramoto model · Randomstrasse101

OP-00053 Solution claimed

The minimum-degree threshold 3/4 for global synchronization

CO · extremal graph theory · global synchronization · Kuramoto model · Randomstrasse101

OP-00054 Solution claimed

The spectral threshold of Kikuchi matrices for tensor PCA

PR · Kikuchi hierarchy · random matrices · Randomstrasse101 · statistical-to-computational gaps · tensor PCA

OP-00055 Solution claimed

Infinitely many square ±1 matrices with discrepancy a constant factor above √n

CO · discrepancy theory · Randomstrasse101 · sign matrices · Spencer's theorem

OP-00056 Solved

The discrepancy of the Sylvester–Hadamard matrices H_k for odd k

CO · Boolean functions · discrepancy theory · Hadamard matrices · Randomstrasse101

OP-00057 Solution claimed

The Lovász number of G(n, 1/2)

CO · Lovász theta function · random graphs · Randomstrasse101 · semidefinite programming

OP-00058 Solution claimed

Maximum cut and maximum bisection of random regular graphs

PR · graph bisection · maximum cut · random regular graphs · Randomstrasse101

OP-00059 Solution claimed

Sharp norm bounds for graph matrices

PR · graph matrices · matrix chaos · random matrices · Randomstrasse101 · Sum-of-Squares

OP-00060 Solution claimed

The value of ω(A) for Gaussian matrices in real phase retrieval

PR · phase retrieval · random matrices · Randomstrasse101 · stability

OP-00061 Solution claimed

The Matrix Spencer conjecture

CO · discrepancy theory · Matrix Spencer · random matrices · Randomstrasse101

OP-00062 Solution claimed

Fitting ellipsoids to random points: the threshold d²/4

PR · ellipsoid fitting · phase transitions · random geometry · Randomstrasse101 · semidefinite programming

OP-00063 Solution claimed

A diverging number of frequencies in multi-frequency synchronization

ST · group synchronization · Randomstrasse101 · spiked random matrices · statistical-to-computational gaps

OP-00064 Solution claimed

The Komlós conjecture

CO · discrepancy theory · Komlós conjecture · Randomstrasse101 · vector balancing

OP-00065 Open

A critical number of frequencies for weak recovery in multi-frequency synchronization

ST · group synchronization · low-degree polynomials · spiked random matrices · statistical-to-computational gaps

OP-00066 Partially resolved

Is the matrix multiplication exponent two?

NA · arithmetic complexity · matrix multiplication · OpenProblemsInNLA

OP-00067 Open

Border rank of the 3×3 matrix product

AG · border rank · matrix multiplication · OpenProblemsInNLA · tensor rank

OP-00068 Open

Strassen's asymptotic rank conjecture for tight tensors

AG · asymptotic rank · matrix multiplication · OpenProblemsInNLA · tensor rank

OP-00069 Open

Knuth–Stolarsky lower bound for addition chains

NT · addition chains · exponentiation · OpenProblemsInNLA

OP-00070 Open

An explicit rational Valiant-rigid matrix family

CO · circuit lower bounds · matrix rigidity · OpenProblemsInNLA

OP-00071 Open

Audenaert's two-row Schatten norm-compression conjecture

FA · block matrices · norm inequalities · OpenProblemsInNLA · Schatten norms

OP-00072 Partially resolved

Minimum number of orthogonal conjugations for diagonal pinching

FA · OpenProblemsInNLA · orthogonal matrices · pinching

OP-00073 Open

Chollet's permanent inequality for Hadamard products

FA · Hadamard product · OpenProblemsInNLA · permanents

OP-00074 Open

Lieb's permanental dominance conjecture

FA · generalized matrix functions · immanants · OpenProblemsInNLA · permanents

OP-00075 Solution claimed

No seven mutually unbiased bases in ℂ⁶

CO · frames · mutually unbiased bases · quantum information · Randomstrasse101

OP-00076 Lean verified

Counting real Hadamard matrices

CO · Hadamard matrices · OpenProblemsInNLA · sign matrices

OP-00077 Lean verified

Is the ideal GMRES bound sharp for every Jordan block?

NA · GMRES · Jordan blocks · Krylov subspace methods · OpenProblemsInNLA

OP-00078 Lean verified

Exponential smoothed tail bounds for partial pivoting

NA · Gaussian elimination · growth factors · OpenProblemsInNLA · smoothed analysis

OP-00079 Lean verified

Exact extremizers for partial pivoting on orthogonal matrices

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

OP-00080 Lean verified

A sharp subset bound for worst-case normal GMRES

NA · GMRES · normal matrices · OpenProblemsInNLA · polynomial approximation

OP-00081 Lean verified

Monotonic optimal backward error along LSMR

NA · backward errors · least-squares problems · LSMR · OpenProblemsInNLA

OP-00082 Lean verified

The exact four-step amplification of restarted Anderson acceleration

NA · Anderson acceleration · convergence factors · fixed-point iterations · OpenProblemsInNLA

OP-00083 Lean verified

Sharp inverse norm bound from upper bounds on matrix entries

NA · diagonally dominant matrices · matrix inverses · OpenProblemsInNLA

OP-00084 Lean verified

Uniqueness of the right inverse minimizing an induced p-to-2 norm

NA · generalized inverses · induced norms · OpenProblemsInNLA

OP-00085 Lean verified

Where a symmetric stochastic matrix can be spectrally unique

NA · doubly stochastic matrices · inverse eigenvalue problems · OpenProblemsInNLA

OP-00086 Lean verified

Johnson's derivative-realizability conjecture

NA · critical points · inverse eigenvalue problems · nonnegative matrices · OpenProblemsInNLA

OP-00087 Lean verified

Polynomial-size vertex test for inverse M-matrix intervals

NA · interval matrices · inverse M-matrices · OpenProblemsInNLA

OP-00088 Lean verified

Number of components of a real interval eigenvalue set

NA · interval matrices · OpenProblemsInNLA · real eigenvalues

OP-00089 Lean verified

Strict interlacing across block Lanczos iterations

NA · block Lanczos methods · eigenvalue interlacing · OpenProblemsInNLA · Ritz values

OP-00090 Lean verified

Local Hölder continuity of the joint spectral radius

DS · Hölder continuity · joint spectral radius · OpenProblemsInNLA

OP-00091 Lean verified

A pointwise Lipschitz lower bound for the joint spectral radius

DS · joint spectral radius · OpenProblemsInNLA · perturbation bounds

OP-00092 Lean verified

Uniform polynomial bounds for products at joint spectral radius one

DS · joint spectral radius · matrix products · OpenProblemsInNLA

OP-00093 Lean verified

Realizing arbitrary polynomial growth exponents by finite matrix families

DS · growth rates · joint spectral radius · matrix products · OpenProblemsInNLA

OP-00094 Lean verified

Degree coverage with seven matrix multiplications

NA · matrix multiplication · matrix polynomials · OpenProblemsInNLA

OP-00095 Lean verified

Imaginary-part rank in a limiting Green-function matrix equation

NA · Green's functions · nonlinear matrix equations · OpenProblemsInNLA · quadratic eigenvalue problems

OP-00096 Lean verified

The uniform expansion threshold for Toeplitz symbols with higher-order zeros

NA · eigenvalue asymptotics · OpenProblemsInNLA · Toeplitz matrices

OP-00097 Lean verified

Polynomial conditioning of the cubic C1 spline Schrödinger Toeplitz family

NA · block Toeplitz matrices · condition numbers · isogeometric analysis · OpenProblemsInNLA

OP-00098 Lean verified

Sharp additive triangle constant for an odd number of contractions

FA · contractions · OpenProblemsInNLA · triangle inequalities

OP-00099 Lean verified

A universal block-norm characterization of essentially Hermitian matrices

FA · block matrices · numerical ranges · OpenProblemsInNLA

OP-00100 Lean verified

Thompson-type domination for the arithmetic symmetric modulus

FA · OpenProblemsInNLA · symmetric moduli · triangle inequalities · unitary orbits