Open problems

1131 registered problems.

OP-00251 Solution claimed

Sharp parameter dependence for structured Gaussian operator norms

PR · OpenProblemsInNLA · operator norms · random matrices

OP-00252 Lean verified

The delta conjecture for minimum symmetric rank

CO · inverse eigenvalue problems · maximum nullity · minimum rank · OpenProblemsInNLA

OP-00253 Lean verified

A chromatic lower bound for positive-semidefinite nullity with SAP

CO · Colin de Verdière parameters · graph colorings · OpenProblemsInNLA · strong Arnold property

OP-00254 Solution claimed

Trace-norm-small perturbations preserve Hermitian spectral distributions

NA · eigenvalue distributions · matrix sequences · non-Hermitian perturbations · OpenProblemsInNLA

OP-00255 Solution claimed

Deciding accurate evaluability of real polynomials

NA · decision procedures · OpenProblemsInNLA · polynomial evaluation · rounding errors

OP-00256 Solution claimed

Recognizing the maximum finite number of solutions

NA · absolute value equations · OpenProblemsInNLA · piecewise linear systems

OP-00257 Solution claimed

Hardness of the spectral-norm condition number

NA · absolute value equations · condition numbers · interval matrices · OpenProblemsInNLA

OP-00258 Solution claimed

Sharp sampling complexity for Walsh restricted isometries

FA · compressed sensing · OpenProblemsInNLA · restricted isometry property · Walsh matrices

OP-00259 Solution claimed

Exact solution hulls for inverse M-matrix intervals

NA · interval matrices · inverse M-matrices · linear systems · OpenProblemsInNLA

OP-00260 Solution claimed

Complexity of globally optimal nonnegative rank-two approximation

NA · low-rank approximations · nonnegative matrix factorizations · OpenProblemsInNLA

OP-00261 Solution claimed

The maximum cp-rank in order six

NA · completely positive matrices · cp-rank · OpenProblemsInNLA

OP-00262 Lean verified

Infinitesimal rigidity detects unique size-two factors in the presence of zeros

NA · infinitesimal rigidity · OpenProblemsInNLA · positive semidefinite factorizations · positive semidefinite rank

OP-00263 Partially resolved

The maximum permanent on a positive-semidefinite unitary orbit

FA · OpenProblemsInNLA · permanents · positive semidefinite matrices · unitary orbits

OP-00264 Partially resolved

Exact determinant ranges of general tridiagonal interval matrices

NA · determinants · interval matrices · OpenProblemsInNLA · tridiagonal matrices

OP-00265 Partially resolved

Exact solution hulls for tridiagonal interval systems

NA · interval matrices · linear systems · OpenProblemsInNLA · tridiagonal matrices

OP-00266 Open

Bourin's crossed-Heinz inequality

FA · norm inequalities · OpenProblemsInNLA · unitarily invariant norms

OP-00267 Open

Localization at every disorder strength in two dimensions

SP · AIM Open Applied Problems · Anderson localization · random Schrödinger operators

OP-00268 Open

Log-concavity of Gaussian convex-hull intersection probabilities

PR · AIM Open Applied Problems · Gaussian random points · log-concave sequences · Radon partitions

OP-00269 Open

Uniqueness of the stationary one-dependent four-coloring

PR · AIM Open Applied Problems · finitely dependent processes · proper colorings

OP-00270 Partially resolved

Pólya's eigenvalue inequalities

SP · AIM Open Applied Problems · Dirichlet eigenvalues · Neumann eigenvalues · Weyl's law

OP-00271 Solution claimed

Tail bounds for causal equivalence classes of uniform random DAGs

PR · AIM Open Applied Problems · directed acyclic graphs · Markov equivalence classes

OP-00272 Open

The spectral honeycomb conjecture

SP · AIM Open Applied Problems · Dirichlet eigenvalues · honeycomb conjecture · spectral minimal partitions

OP-00273 Open

The regular-polygon Steklov conjecture

SP · AIM Open Applied Problems · isoperimetric inequalities · polygons · Steklov eigenvalues

OP-00274 Solution claimed

Sharp least-singular-value bounds for independent random tensor columns

PR · AIM Open Applied Problems · random matrices · random tensors · singular values

OP-00275 Open

Bareket's conjecture for simply connected planar domains

SP · AIM Open Applied Problems · isoperimetric inequalities · Robin eigenvalues

OP-00276 Open

Polynomial-time Bernoulli group testing at the information threshold

ST · AIM Open Applied Problems · computational-statistical gaps · group testing

OP-00277 Open

Berry's random-wave conjecture as a local limit

SP · AIM Open Applied Problems · Laplace eigenfunctions · quantum chaos · random waves

OP-00278 Open

Support growth of the information-maximizing binomial prior

IT · AIM Open Applied Problems · capacity-achieving distributions · channel capacity

OP-00279 Open

A degree-two spectral gap for Brownian energy exchange

PR · AIM Open Applied Problems · Brownian energy process · interacting particle systems · spectral gaps

OP-00280 Open

The sharp ratio of the first two buckling eigenvalues

SP · AIM Open Applied Problems · buckling eigenvalues · clamped plates · eigenvalue ratios

OP-00281 Solution claimed

Pólya–Szegő conjecture for the first buckling load

SP · AIM Open Applied Problems · buckling eigenvalues · clamped plates · isoperimetric inequalities

OP-00282 Open

Hypergraph shuffles and the one-particle spectral gap

PR · AIM Open Applied Problems · hypergraphs · interchange process · spectral gaps

OP-00283 Open

Separation of measures by Cartan–Hadamard sliced distances

PR · AIM Open Applied Problems · Cartan–Hadamard manifolds · Radon transforms · sliced Wasserstein distances

OP-00284 Open

Polynomial-time DNF learning from uniform random examples

ST · AIM Open Applied Problems · Boolean functions · DNF formulas · PAC learning

OP-00285 Open

Dirichlet spectral determination of smooth strictly convex planar domains

SP · AIM Open Applied Problems · Dirichlet eigenvalues · inverse spectral problems · isospectral domains

OP-00286 Open

A fractal Weyl lower bound for obstacle resonances

SP · AIM Open Applied Problems · fractal Weyl laws · obstacle scattering · scattering resonances

OP-00287 Open

Orthogonal separation of independent Gaussian polynomial statistics

PR · AIM Open Applied Problems · characterization problems · Gaussian vectors · independence

OP-00288 Open

Ordinary posterior contraction for heavy-tailed neural-network priors

ST · AIM Open Applied Problems · Bayesian neural networks · heavy-tailed priors · posterior contraction

OP-00289 Open

Minimax entropy estimation beyond two derivatives

ST · AIM Open Applied Problems · differential entropy · functional estimation · minimax rates

OP-00290 Open

Ivrii's measure-zero conjecture for billiards

DS · AIM Open Applied Problems · billiards · periodic orbits · Weyl's law

OP-00291 Open

Classical hardness of learning parity with noise

IT · AIM Open Applied Problems · average-case complexity · learning parity with noise · random linear codes

OP-00292 Open

The three-dimensional Lieb–Thirring constant

SP · AIM Open Applied Problems · Lieb–Thirring inequalities · Schrödinger operators · sharp constants

OP-00293 Open

Linear-size sample compression for binary concept classes

CO · AIM Open Applied Problems · sample compression schemes · VC dimension

OP-00294 Open

Identifying a distribution from its Gaussian-channel MMSE curve

PR · AIM Open Applied Problems · Gaussian channels · minimum mean-square error

OP-00295 Open

The planar self-avoiding-walk displacement exponent

PR · AIM Open Applied Problems · critical exponents · self-avoiding walks

OP-00296 Open

Pólya–Szegő polygonal Faber–Krahn conjecture

SP · AIM Open Applied Problems · Dirichlet eigenvalues · Faber–Krahn inequality · polygons

OP-00297 Open

The polygonal Payne–Pólya–Weinberger ratio conjecture

SP · AIM Open Applied Problems · Dirichlet eigenvalues · eigenvalue ratios · polygons

OP-00298 Open

Oscillation of partition functions under very strong disorder

PR · AIM Open Applied Problems · directed polymers · random walks in random potentials

OP-00299 Open

Private PAC learning with polynomial VC and iterated-logarithm sample cost

ST · AIM Open Applied Problems · differential privacy · Littlestone dimension · PAC learning

OP-00300 Open

Perfect recovery threshold for unregularized quadratic-network training

PR · AIM Open Applied Problems · gradient flows · matrix sensing · quadratic neural networks