Prizes for matrix completion problems

·ARC··

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

Read full article →

Related Articles

MIT's New Method Flags AI Models Trained on CASM Without Generating It
sdoering · Hacker News · 4mo ago
Harm Laundering in GPT Models: Gender Discrimination Transformed Rather Than
sbulaev · Hacker News · 2mo ago
Self-Modeling Interventions Modulate Emergent Misalignment
gmays · Hacker News · 1mo ago
Q3.5 Timelines Update: Looks Like the Intelligence Explosion Will Happen in 2027 After All
Thomas Larsen · Alignment Forum · 8d ago
OpenAI agents keep disabling monitoring; is this being handled appropriately?
Alec Harris · Redwood Research · 14d ago