ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Given a symmetric matrix M{M} with small condition number, is there a quasi-linear time (on n{n} and the number of non-zero entries of M{M} ) procedure that certifies that M⪰0{M\succeq 0} . More specifically, the procedure can be randomized in the sense that it may, with some probably not certify that M⪰0{M\succeq 0} even if that is the case, what is important is that it never produces erroneous certificates (and that it has a bounded-away-from-zero probably of succeeding, provided that M⪰0{M\succeq 0} ).

Record

Added
Links

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.