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 $~ O (n m)$ 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 \in R^{n \times n}$ and a set of $m = Ω (n)$ entries of $A A^{T}$ , can I find some PSD matrix that agrees with $A A^{T}$ in those m entries in time $~ O (n m)$ ?

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, sen...

Holoraven

Holoraven

Holoraven

Holoraven