open_problem: ax-2605.05076-e89f0364

This data as json

id statement domain sourced_how source_url cheapest_test status claimed_by sourced_by shape created_ts updated_ts
ax-2605.05076-e89f0364 2.5 Further open directions: • Gaps at the level of constants. Most existing work characterizes computational-statistical gaps in terms of rates. However, for problems such as estimating a rank-1 spike in a Gaussian matrix, the gap between information-theoretically optimal and computationally efficient methods manifests at the level of sharp constants—specifically, the precise SNR threshold. It is widely believed that approximate message passing (AMP) algorithms achieve the optimal SNR threshold among efficient methods, but rigorous evidence remains limited: current low-degree lower bounds only rule out constant-degree polynomials rather than the logarithmic-degree polynomials that would provide stronger evidence. Understanding when AMP is optimal among efficient procedures, and extending constant-level gap analyses more broadly, is an important open direction. See for recent progress in this direction. mathematics / math.ST enumerated in arXiv paper titled 'open problems' (prose (list items and question sentences under an open-problems heading)): High-Dimensional Statistics: Reflections on Progress and Open Problems https://arxiv.org/abs/2605.05076   open   ts-synth needs-theory 2026-09-02T17:57:21Z 2026-09-02T17:57:21Z

Links from other tables