{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:28Z","timestamp":1781031448227,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"MathWorks Fellowship","award":["MathWorks Fellowship"],"award-info":[{"award-number":["MathWorks Fellowship"]}]},{"name":"NSF Graduate Research Fellowship","award":["DGE-2146752"],"award-info":[{"award-number":["DGE-2146752"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800830","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1192-1199","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Markov Chains Approximate Message Passing"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9460-0725","authenticated-orcid":false,"given":"Amit","family":"Rajaraman","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4863-4689","authenticated-orcid":false,"given":"David X.","family":"Wu","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649622"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/aafa7d"},{"key":"e_1_3_2_1_3_1","volume-title":"G\u00e9rard Ben Arous, and Sandrine P\u00e9ch\u00e9","author":"Baik Jinho","year":"2005","unstructured":"Jinho Baik, G\u00e9rard Ben Arous, and Sandrine P\u00e9ch\u00e9. 2005. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2094817"},{"key":"e_1_3_2_1_5_1","volume-title":"Cugliandolo-Kurchan equations for dynamics of spin-glasses. Probability theory and related fields, 136, 4","author":"Arous G\u00e9rard Ben","year":"2006","unstructured":"G\u00e9rard Ben Arous, Amir Dembo, and Alice Guionnet. 2006. Cugliandolo-Kurchan equations for dynamics of spin-glasses. Probability theory and related fields, 136, 4 (2006), 619\u2013660."},{"key":"e_1_3_2_1_6_1","unstructured":"G\u00e9rard Ben Arous C\u00e9dric Gerbelot and Vanessa Piccolo. 2024. Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA. arXiv preprint arXiv:2408.06401."},{"key":"e_1_3_2_1_7_1","first-page":"2052","article-title":"Algorithmic thresholds for tensor PCA","volume":"48","author":"Arous Gerard Ben","year":"2020","unstructured":"Gerard Ben Arous, Reza Gheissari, and Aukosh Jagannath. 2020. Algorithmic thresholds for tensor PCA. The Annals of Probability, 48, 4 (2020), 2052\u20132087.","journal-title":"The Annals of Probability"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.22133"},{"key":"e_1_3_2_1_9_1","unstructured":"Thiago Bergamaschi Chi-Fang Chen and Umesh Vazirani. 2025. A Structural Theory of Quantum Metastability: Markov Properties and Area Laws. arXiv preprint arXiv:2510.08538."},{"key":"e_1_3_2_1_10_1","volume-title":"Metastability: a potential-theoretic approach. 351","author":"Bovier Anton","unstructured":"Anton Bovier and Frank Den Hollander. 2016. Metastability: a potential-theoretic approach. 351, Springer."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00018"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.71.173"},{"key":"e_1_3_2_1_13_1","unstructured":"Yatin Dandi David Gamarnik Francisco Pernice and Lenka Zdeborov\u00e1. 2025. Sequential Dynamics in Ising Spin Glasses. arXiv preprint arXiv:2506.09877."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/11\/5\/028"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","unstructured":"Yash Deshpande Emmanuel Abbe and Andrea Montanari. 2016. Asymptotic mutual information for the binary stochastic block model. 07 185\u2013189. https:\/\/doi.org\/10.1109\/ISIT.2016.7541286 10.1109\/ISIT.2016.7541286","DOI":"10.1109\/ISIT.2016.7541286"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875223"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-023-04742-5"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0909892106"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Ahmed El Alaoui Florent Krzakala and Michael Jordan. 2020. Fundamental limits of detection in the spiked Wigner model.","DOI":"10.1214\/19-AOS1826"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00038"},{"key":"e_1_3_2_1_22_1","volume-title":"A spectral condition for spectral gap: fast mixing in high-temperature Ising models. Probability theory and related fields, 182, 3","author":"Eldan Ronen","year":"2022","unstructured":"Ronen Eldan, Frederic Koehler, and Ofer Zeitouni. 2022. A spectral condition for spectral gap: fast mixing in high-temperature Ising models. Probability theory and related fields, 182, 3 (2022), 1035\u20131051."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026124"},{"key":"e_1_3_2_1_24_1","unstructured":"Brice Huang Andrea Montanari and Huy Tuan Pham. 2024. Sampling from spherical spin glasses in total variation via algorithmic stochastic localization. arXiv preprint arXiv:2404.15651."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.3.77"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Pravesh K Kothari and Jeff Xu. 2025. Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices. arXiv preprint arXiv:2510.03061.","DOI":"10.1137\/1.9781611978971.95"},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory. 2993\u20133050","author":"Lee Yin Tat","year":"2021","unstructured":"Yin Tat Lee, Ruoqi Shen, and Kevin Tian. 2021. Structured logconcave sampling with a restricted Gaussian oracle. In Conference on Learning Theory. 2993\u20133050."},{"key":"e_1_3_2_1_28_1","volume-title":"Conference on Learning Theory. 1297\u20131301","author":"Lelarge Marc","year":"2017","unstructured":"Marc Lelarge and L\u00e9o Miolane. 2017. Fundamental limits of symmetric low-rank matrix estimation. In Conference on Learning Theory. 1297\u20131301."},{"key":"e_1_3_2_1_29_1","unstructured":"Gen Li and Yuting Wei. 2022. A non-asymptotic framework for approximate message passing in spiked models. arXiv preprint arXiv:2208.03313."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Tengyuan Liang Subhabrata Sen and Pragya Sur. 2022. High-dimensional asymptotics of Langevin dynamics in spiked matrix models. arXiv preprint arXiv:2204.04476.","DOI":"10.1093\/imaiai\/iaad042"},{"key":"e_1_3_2_1_31_1","volume-title":"Wu","author":"Liu Kuikui","year":"2024","unstructured":"Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, and David X. Wu. 2024. Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. arxiv:2405.20849."},{"key":"e_1_3_2_1_32_1","volume-title":"Fast Mixing in Sparse Random Ising Models. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). 120\u2013128","author":"Liu Kuikui","year":"2024","unstructured":"Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, and David X Wu. 2024. Fast Mixing in Sparse Random Ising Models. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). 120\u2013128."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1142\/0271"},{"key":"e_1_3_2_1_34_1","unstructured":"L\u00e9o Miolane. 2017. Fundamental limits of low-rank matrix estimation: the non-symmetric case. arXiv preprint arXiv:1702.00473."},{"key":"e_1_3_2_1_35_1","volume-title":"A statistical model for tensor PCA. Advances in neural information processing systems, 27","author":"Montanari Andrea","year":"2014","unstructured":"Andrea Montanari and Emile Richard. 2014. A statistical model for tensor PCA. Advances in neural information processing systems, 27 (2014)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2457942"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Andrea Montanari and Ramji Venkataramanan. 2021. Estimation of low-rank matrices via approximate message passing.","DOI":"10.1214\/20-AOS1958"},{"key":"e_1_3_2_1_38_1","unstructured":"Andrea Montanari and Yuchen Wu. 2023. Posterior sampling in high dimension via diffusion processes. arXiv preprint arXiv:2304.11449."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1625"},{"key":"e_1_3_2_1_40_1","unstructured":"Dhruv Rohatgi Abhishek Shetty Donya Saless Yuchen Li Ankur Moitra Andrej Risteski and Dylan J Foster. 2025. Taming Imperfect Process Verifiers: A Sampling Perspective on Backtracking. arXiv preprint arXiv:2510.03149."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2816681"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.22197"},{"key":"e_1_3_2_1_43_1","unstructured":"Ruoqi Shen Kevin Tian and Yin Tat Lee. 2020. Composite Logconcave Sampling with a Restricted Gaussian Oracle. arXiv preprint arXiv:2006.05976."},{"key":"e_1_3_2_1_44_1","first-page":"416","article-title":"On a method of calculating quantum distribution functions","volume":"2","author":"Stratonovich RL","year":"1957","unstructured":"RL Stratonovich. 1957. On a method of calculating quantum distribution functions. In Soviet Physics Doklady. 2, 416.","journal-title":"Soviet Physics Doklady."},{"key":"e_1_3_2_1_45_1","volume-title":"Ahmed El Alaoui, and Cristopher Moore","author":"Wein Alexander","year":"2019","unstructured":"Alexander Wein, Ahmed El Alaoui, and Cristopher Moore. 2019. The Kikuchi hierarchy and tensor PCA. J. ACM."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800830","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:03:11Z","timestamp":1781028191000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800830"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":45,"alternative-id":["10.1145\/3798129.3800830","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800830","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}