2 papers
cs.LG2026
Sharp Low-Degree Thresholds for Planted-vs-Planted Testing
Anda Skeja, Daniel Gutiérrez Espinoza, Fiona Skerman +1
We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured…
cs.DS2025
Improving the Threshold for Finding Rank-1 Matrices in a Subspace
Jeshu Dastidar, Tait Weicht, Alexander S. Wein
We consider a basic computational task of finding planted rank-1 matrices in a linear subspace where $\dim(\mathcal…