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 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.
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×n matrix, including the diagonal, can we tell in time ~O(nm) whether it has any (real, symmetric) positive semidefinite completion? Proving that this task is at least as hard as dense matrix multiplication or PSD testing would count as a resolution.
Question 2 (fast “approximate squaring”): given A∈Rn×n and a set of m=Ω(n) entries of AAT, can I find some PSD matrix that agrees with AAT in those m entries in time ~O(nm)?
We'll pay $5k for a solution to either problem. The offer is open for each problem for 3 months or until the problem gets solved (whichever happens first). Winners are welcome to publish solutions independently. Otherwise, if the result ends up being a significant part of a paper, we’ll invite them to be a coauthor.
We’ll also consider smaller prizes for partial progress, or anything that we find helpful for either solving the problem or realizing we should give up on it.
To understand the motivation for these questions, you can read our paper on Formalizing the presumption of independence and in particular Appendix D.7.2. ARC is trying to find efficient heuristic estimators as a formalization of defeasible reasoning about quantities like the variance of a neural network's output. These two questions are very closely related to one of the simplest cases where we haven't yet found any reasonable linear time heuristic estimator.
We don’t expect to receive many incorrect proposals, but if we receive more than 5 we may start applying a higher standard in order to save our time. If we can’t understand a solution quickly, we may ask you to provide more details, and if we still can’t understand it we may reject it. We expect a correct solution to be about as clear and easy to verify as a paper published at STOC.
For both problems, it’s OK if we incorrectly treat a matrix as PSD as long as all of its eigenvalues are at least −ε for a small constant ε. ~O hides polylogarithmic factors in n, ε, and the max matrix entry. Feel free to ask for other clarifications on our question on Math Overflow, on Facebook, or by email.
To submit a solution, send an email to prize@alignment.org.