6 papers
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…
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…
Stochastic block models with many communities and the Kesten--Stigum bound
Byron Chin, Elchanan Mossel, Youngtak Sohn +1
We study the inference of communities in stochastic block models with a growing number of communities. For block models with vertices and a fixed number of communities , it…
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
Youngtak Sohn, Alexander S. Wein
High-dimensional planted problems, such as finding a hidden dense subgraph within a random graph, often exhibit a gap between statistical and computational feasibility. While recov…
Low-degree phase transitions for detecting a planted clique in sublinear time
Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein
We consider the problem of detecting a planted clique of size in a random graph on vertices. When the size of the clique exceeds , polynomial-time algorithms f…
Time Lower Bounds for the Metropolis Process and Simulated Annealing
Zongchen Chen, Dan Mikulincer, Daniel Reichman +1
The Metropolis process (MP) and Simulated Annealing (SA) are stochastic local search heuristics that are often used in solving combinatorial optimization problems. Despite signific…