Alexander S. Wein

activity

20232026

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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 $s$ planted rank-1 $m \times n$ matrices in a linear subspace $U \subseteq R^{m \times n}$ where $\dim(\mathcal…

cs.DS2024

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 $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $Θ (n)$ , polynomial-time algorithms f…

cs.DS2023

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…