10 Lectures and 42 Open Problems — Certifying that matrices are PSD
Statement
Given a symmetric matrix with small condition number, is there a quasi-linear time (on and the number of non-zero entries of ) procedure that certifies that . More specifically, the procedure can be randomized in the sense that it may, with some probably not certify that 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 ).
Record
- Source
- Added
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.