STOC Conference 2025 Conference Paper
Fast, Robust Approximate Message Passing
- Misha Ivkov
- Tselil Schramm
Author name cluster
Misha Ivkov
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
3 papers
1 author row
Possible papers
3STOC Conference 2024 Conference Paper
Semidefinite Programs Simulate Approximate Message Passing Robustly
- Misha Ivkov
- Tselil Schramm
Approximate message passing (AMP) is a family of iterative algorithms that generalize matrix power iteration. AMP algorithms are known to optimally solve many average-case optimization problems. In this paper, we show that a large class of AMP algorithms can be simulated in polynomial time by local statistics hierarchy semidefinite programs (SDPs), even when an unknown principal minor of measure 1/ polylog ( dimension ) is adversarially corrupted. Ours are the first robust guarantees for many of these problems. Further, our results offer an interesting counterpoint to strong lower bounds against less constrained SDP relaxations for average-case max-cut-gain (a.k.a. “optimizing the Sherrington-Kirkpatrick Hamiltonian”) and other problems.
STOC Conference 2022 Conference Paper
List-decodable covariance estimation
- Misha Ivkov
- Pravesh K. Kothari