We intend to leave this prize open until the end of September. At that point we will distribute prizes (probably just small prizes for useful arguments and algorithms, but no full solution).
I now pretty strongly suspect that the version of problem 1 with logarithmic dependence on ε is not solvable. We would award a prize for an algorithm running in time O(mnε−1) which can distinguish matrices with no PSD completion from those with a completion where the ratio of min to max eigenvalue is at least ε. And of course a lower bound is still fair game.
That said, I don’t expect any new submissions to win prizes and so wouldn’t recommend that anyone start working on it.
We intend to leave this prize open until the end of September. At that point we will distribute prizes (probably just small prizes for useful arguments and algorithms, but no full solution).
I now pretty strongly suspect that the version of problem 1 with logarithmic dependence on ε is not solvable. We would award a prize for an algorithm running in time O(mnε−1) which can distinguish matrices with no PSD completion from those with a completion where the ratio of min to max eigenvalue is at least ε. And of course a lower bound is still fair game.
That said, I don’t expect any new submissions to win prizes and so wouldn’t recommend that anyone start working on it.