\u672c\u6587\u9810\u89bd<\/a><\/p>\n\n\n\n\u4f5c\u8005<\/strong>\u3000\u4f3d\u99ac\u5c3c\u514b\uff08David Gamarnik\uff09<\/p>\n\n\n\n\u4f5c\u8005\u7c21\u4ecb<\/strong>
\u4f3d\u99ac\u5c3c\u514b\u662fMIT\u53f2\u9686\u7ba1\u7406\u5b78\u9662\u7684\u4f5c\u696d\u7814\u7a76\u548c\u7d71\u8a08\u6559\u6388\u3002\u4ed6\u7684\u7814\u7a76\u9818\u57df\u5305\u62ec\u96e2\u6563\u6a5f\u7387\u3001\u6700\u4f73\u5316\u8207\u6f14\u7b97\u6cd5\u3001\u91cf\u5b50\u8a08\u7b97\u3001\u7d71\u8a08\u3001\u6a5f\u5668\u5b78\u7fd2\u548c\u96a8\u6a5f\u904e\u7a0b\u3002<\/p>\n\n\n\n\u8b6f\u8005<\/strong>\u3000\u6797\u6b66\u96c4<\/p>\n\n\n\n\u8b6f\u8005\u7c21\u4ecb<\/strong>
\u6797\u6b66\u96c4\u662f\u570b\u7acb\u967d\u660e\u4ea4\u901a\u5927\u5b78\u61c9\u7528\u6578\u5b78\u7cfb\u52a9\u7406\u6559\u6388\u3002<\/p>\n\n\n\n\u672c\u6587\u51fa\u8655<\/strong>
\u672c\u6587\u8b6f\u81eaDavid Gamarnik,\u201cTuring in the Shadows of Nobel and Abel: An Algorithmic Story Behind Two Recent Prizes\u201d, Notices of the AMS 72\uff082025\uff09No. 5, AMS\u3002\u00a9 American Mathematical Society 2008. All rights reserved\u3002\u611f\u8b1dAMS\u8207\u4f5c\u8005\u540c\u610f\u8f49\u8f09\u7ffb\u8b6f\u3002<\/p>\n\n\n\n\u5ef6\u4f38\u95b1\u8b80<\/strong>
\u8b80\u8005\u53ef\u53c3\u7d39\u672c\u520a\u7b2c27\u671f\u7684\u3008\u8a08\u7b97\u8907\u96dc\u6027\u7406\u8ad6\u768450\u5e74\u77e5\u8b58\u6975\u9650\u4e4b\u65c5\u3009\u4e00\u6587\u95b1\u8b80\u3002<\/p>\n\n\n\n\u53c3\u8003\u6587\u737b<\/strong>
[ART06] Dimitris Achlioptas and Federico Ricci-Tersenghi, On the solution-space geometry of random constraint satisfaction problems, STOC\u201906: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, ACM, New York, 2006, pp. 130\u2013139.
[BH22] Guy Bresler and Brice Huang, The algorithmic phase transition of random \ud835\udc58-SAT for low degree polynomials, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science\u2014FOCS 2021, IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 298\u2013309.
[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\u20131618.
[CO10] Amin Coja-Oghlan, A better algorithm for random \ud835\udc58-SAT, SIAM J. Comput. 39 (2010), no. 7, 2823\u20132864.
[DSS22] Jian Ding, Allan Sly, and Nike Sun, Proof of the satisfiability conjecture for large \ud835\udc58, Ann. of Math. (2) 196 (2022), no. 1, 1\u2013388.
[EAMS21] Ahmed El Alaoui, Andrea Montanari, and Mark Sellke, Optimization of mean-field spin glasses, Ann. Probab. 49 (2021), no. 6, 2922\u20132960.
[Fri90] A. M. Frieze, On the independence number of random graphs, Discrete Math. 81 (1990), no. 2, 171\u2013175.
[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\u201346.
[GKPX22] David Gamarnik, Eren C. K\u0131z\u0131lda\u011f, Will Perkins, and Changji Xu, Algorithms and barriers in the symmetric binary perceptron model, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science\u2014FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 576\u2013587.
[GMZ22] David Gamarnik, Cristopher Moore, and Lenka Zdeborov\u00e1, 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\u20132376.
[Gue03] Francesco Guerra, Broken replica symmetry bounds in the mean field spin glass model, Comm. Math. Phys. 233 (2003), no. 1, 1\u201312.
[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\u2014FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, 2022, pp. 312\u2013322.
[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\u201319.
[MMZ05] M. M\u00e9zard, 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\u2013Kirkpatrick Hamiltonian, 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. Press, Los Alamitos, CA, 2019, pp. 1417\u20131433,
[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\u00e1lint Vir\u00e1g, Local algorithms for independent sets are half-optimal, Ann. Probab. 45 (2017), no. 3, 1543\u20131577.
[Sub21] Eliran Subag, Following the ground states of full-RSB spherical spin glasses, Comm. Pure Appl. Math. 74 (2021), no. 5, 1021\u20131044.
[Tal06] Michel Talagrand, The Parisi formula, Ann. of Math. (2) 163 (2006), no. 1, 221\u2013263.<\/p>\n\n\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"
\u8afe\u8c9d\u723e\u8207\u963f\u8c9d\u723e\u7684\u5149\u74b0\u4e0b\u7684\u6d82\u6797 \u672c\u6587\u9810\u89bd \u4f5c\u8005\u3000\u4f3d\u99ac\u5c3c\u514b\uff08David Gamarnik\uff09 \u4f5c\u8005\u7c21\u4ecb\u4f3d\u99ac\u5c3c\u514b\u662fMI […]<\/p>\n","protected":false},"author":7,"featured_media":0,"parent":3973,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3979","page","type-page","status-publish","hentry","entry"],"yoast_head":"\n
\u6578\u7406\u4eba\u6587030_01 - \u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/deptweb.cycu.edu.tw\/qic\/\u6578\u7406\u4eba\u6587\/\u6578\u7406\u4eba\u6587030\/\u6578\u7406\u4eba\u6587030_01\/\" \/>\n<meta property=\"og:locale\" content=\"zh_TW\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u6578\u7406\u4eba\u6587030_01 - \u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3\" \/>\n<meta property=\"og:description\" content=\"\u8afe\u8c9d\u723e\u8207\u963f\u8c9d\u723e\u7684\u5149\u74b0\u4e0b\u7684\u6d82\u6797 \u672c\u6587\u9810\u89bd \u4f5c\u8005\u3000\u4f3d\u99ac\u5c3c\u514b\uff08David Gamarnik\uff09 \u4f5c\u8005\u7c21\u4ecb\u4f3d\u99ac\u5c3c\u514b\u662fMI […]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/deptweb.cycu.edu.tw\/qic\/\u6578\u7406\u4eba\u6587\/\u6578\u7406\u4eba\u6587030\/\u6578\u7406\u4eba\u6587030_01\/\" \/>\n<meta property=\"og:site_name\" content=\"\u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3\" \/>\n<meta property=\"article:modified_time\" content=\"2026-07-23T03:40:35+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"\u9810\u4f30\u95b1\u8b80\u6642\u9593\" \/>\n\t<meta name=\"twitter:data1\" content=\"4 \u5206\u9418\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/\",\"url\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/\",\"name\":\"\u6578\u7406\u4eba\u6587030_01 - \u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3\",\"isPartOf\":{\"@id\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/#website\"},\"datePublished\":\"2026-07-23T02:17:37+00:00\",\"dateModified\":\"2026-07-23T03:40:35+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/#breadcrumb\"},\"inLanguage\":\"zh-TW\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u6578\u7406\u4eba\u6587\",\"item\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u6578\u7406\u4eba\u6587030\",\"item\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"\u6578\u7406\u4eba\u6587030_01\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/#website\",\"url\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/\",\"name\":\"\u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3\",\"description\":\"\u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/deptweb.cycu.edu.tw\/qic\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"zh-TW\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u6578\u7406\u4eba\u6587030_01 - \u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/deptweb.cycu.edu.tw\/qic\/\u6578\u7406\u4eba\u6587\/\u6578\u7406\u4eba\u6587030\/\u6578\u7406\u4eba\u6587030_01\/","og_locale":"zh_TW","og_type":"article","og_title":"\u6578\u7406\u4eba\u6587030_01 - \u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3","og_description":"\u8afe\u8c9d\u723e\u8207\u963f\u8c9d\u723e\u7684\u5149\u74b0\u4e0b\u7684\u6d82\u6797 \u672c\u6587\u9810\u89bd \u4f5c\u8005\u3000\u4f3d\u99ac\u5c3c\u514b\uff08David Gamarnik\uff09 \u4f5c\u8005\u7c21\u4ecb\u4f3d\u99ac\u5c3c\u514b\u662fMI […]","og_url":"https:\/\/deptweb.cycu.edu.tw\/qic\/\u6578\u7406\u4eba\u6587\/\u6578\u7406\u4eba\u6587030\/\u6578\u7406\u4eba\u6587030_01\/","og_site_name":"\u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3","article_modified_time":"2026-07-23T03:40:35+00:00","twitter_card":"summary_large_image","twitter_misc":{"\u9810\u4f30\u95b1\u8b80\u6642\u9593":"4 \u5206\u9418"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/","url":"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/","name":"\u6578\u7406\u4eba\u6587030_01 - \u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3","isPartOf":{"@id":"https:\/\/deptweb.cycu.edu.tw\/qic\/#website"},"datePublished":"2026-07-23T02:17:37+00:00","dateModified":"2026-07-23T03:40:35+00:00","breadcrumb":{"@id":"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/#breadcrumb"},"inLanguage":"zh-TW","potentialAction":[{"@type":"ReadAction","target":["https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030_01\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u6578\u7406\u4eba\u6587","item":"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/"},{"@type":"ListItem","position":2,"name":"\u6578\u7406\u4eba\u6587030","item":"https:\/\/deptweb.cycu.edu.tw\/qic\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87\/%e6%95%b8%e7%90%86%e4%ba%ba%e6%96%87030\/"},{"@type":"ListItem","position":3,"name":"\u6578\u7406\u4eba\u6587030_01"}]},{"@type":"WebSite","@id":"https:\/\/deptweb.cycu.edu.tw\/qic\/#website","url":"https:\/\/deptweb.cycu.edu.tw\/qic\/","name":"\u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3","description":"\u4e2d\u539f\u5927\u5b78\u91cf\u5b50\u8cc7\u8a0a\u4e2d\u5fc3","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/deptweb.cycu.edu.tw\/qic\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"zh-TW"}]}},"_links":{"self":[{"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/pages\/3979"}],"collection":[{"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/comments?post=3979"}],"version-history":[{"count":2,"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/pages\/3979\/revisions"}],"predecessor-version":[{"id":3983,"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/pages\/3979\/revisions\/3983"}],"up":[{"embeddable":true,"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/pages\/3973"}],"wp:attachment":[{"href":"https:\/\/deptweb.cycu.edu.tw\/qic\/wp-json\/wp\/v2\/media?parent=3979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}