諾貝爾與阿貝爾的光環下的涂林
作者 伽馬尼克（David Gamarnik）
作者簡介
伽馬尼克是MIT史隆管理學院的作業研究和統計教授。他的研究領域包括離散機率、最佳化與演算法、量子計算、統計、機器學習和隨機過程。
譯者 林武雄
譯者簡介
林武雄是國立陽明交通大學應用數學系助理教授。
本文出處
本文譯自David Gamarnik,“Turing in the Shadows of Nobel and Abel: An Algorithmic Story Behind Two Recent Prizes”, Notices of the AMS 72（2025）No. 5, AMS。© American Mathematical Society 2008. All rights reserved。感謝AMS與作者同意轉載翻譯。
延伸閱讀
讀者可參紹本刊第27期的〈計算複雜性理論的50年知識極限之旅〉一文閱讀。
參考文獻
[ART06] Dimitris Achlioptas and Federico Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 130–139.
[BH22] Guy Bresler and Brice Huang, The algorithmic phase transition of random 𝑘-SAT for low degree polynomials, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science—FOCS 2021, IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 298–309.
[CMM+23] Patrick Charbonneau, Enzo Marinari, Marc Mezard, Giorgio Parisi, Federico Ricci-Tersenghi, Gabriele Sicuro, and Francesco Zamponi (eds.), Spin glass theory and far beyond: replica symmetry breaking after 40 years, World Scientific, 2023.
[CGPR19] Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman, Suboptimality of local algorithms for a class of max-cut problems, Ann. Probab. 47 (2019), no. 3, 1587–1618.
[CO10] Amin Coja-Oghlan, A better algorithm for random 𝑘-SAT, SIAM J. Comput. 39 (2010), no. 7, 2823–2864.
[DSS22] Jian Ding, Allan Sly, and Nike Sun, Proof of the satisfiability conjecture for large 𝑘, Ann. of Math. (2) 196 (2022), no. 1, 1–388.
[EAMS21] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke, Optimization of mean-field spin glasses, Ann. Probab. 49 (2021), no. 6, 2922–2960.
[Fri90] A. M. Frieze, On the independence number of random graphs, Discrete Math. 81 (1990), no. 2, 171–175.
[GJW24] David Gamarnik, Aukosh Jagannath, and Alexander S. Wein, Hardness of random optimization problems for Boolean circuits, low-degree polynomials, and Langevin dynamics, SIAM J. Comput. 53 (2024), no. 1, 1–46.
[GKPX22] David Gamarnik, Eren C. Kızıldağ, Will Perkins, and Changji Xu, Algorithms and barriers in the symmetric binary perceptron model, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 576–587.
[GMZ22] David Gamarnik, Cristopher Moore, and Lenka Zdeborová, Disordered systems insights on computational hardness, J. Stat. Mech. Theory Exp. 11 (2022), Paper No. 114015, 41.
[GS17] David Gamarnik and Madhu Sudan, Limits of local algorithms over sparse random graphs, Ann. Probab. 45 (2017), no. 4, 2353–2376.
[Gue03] Francesco Guerra, Broken replica symmetry bounds in the mean field spin glass model, Comm. Math. Phys. 233 (2003), no. 1, 1–12.
[HS22] Brice Huang and Mark Sellke, Tight Lipschitz hardness for optimizing mean field spin glasses, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 312–322.
[Kar76] Richard M. Karp, The probabilistic analysis of some combinatorial search algorithms, Algorithms and complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1976), Academic Press, New York-London, 1976, pp. 1–19.
[MMZ05] M. Mézard, T. Mora, and R. Zecchina, Clustering of solutions in the random satisfiability problem, Physical Review Letters 94 (2005), no. 19, 197-205.
[Mon19] Andrea Montanari, Optimization of the Sherrington–Kirkpatrick Hamiltonian, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 2019, pp. 1417–1433,
[Par80] Giorgio Parisi, A sequence of approximated solutions to the SK model for spin glasses, J. Phys. A: Math. Gen. 13 (1980), no. 4, L115.
[RV17] Mustazee Rahman and Bálint Virág, Local algorithms for independent sets are half-optimal, Ann. Probab. 45 (2017), no. 3, 1543–1577.
[Sub21] Eliran Subag, Following the ground states of full-RSB spherical spin glasses, Comm. Pure Appl. Math. 74 (2021), no. 5, 1021–1044.
[Tal06] Michel Talagrand, The Parisi formula, Ann. of Math. (2) 163 (2006), no. 1, 221–263.
