Prizes for matrix completion problems

Here are two self-contained algorithmic questions that have come up in our research. We're offering a bounty of $5k for a solution to either of them—either an algorithm, or a lower bound under any hardness assumption that has appeared in the literature.Question 1 (existence of PSD completions): given \(m\) entries of an \(n \times n\) matrix, including the diagonal, can we tell in time \(\tilde{O}(nm)\) whether it has any (real, symmetric) positive semidefinite completion? Proving that this...