{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:46Z","timestamp":1781077846012,"version":"3.54.1"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"Simons-Berkeley Research Fellowship"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["RGPIN-2020-04597"],"award-info":[{"award-number":["RGPIN-2020-04597"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["DGECR-2020-00199"],"award-info":[{"award-number":["DGECR-2020-00199"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2015517"],"award-info":[{"award-number":["DMS-2015517"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1712730"],"award-info":[{"award-number":["DMS-1712730"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2007443"],"award-info":[{"award-number":["CCF-2007443"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2106444"],"award-info":[{"award-number":["CCF-2106444"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,2,29]]},"DOI":"10.1137\/22m150263x","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T09:59:03Z","timestamp":1707818343000},"page":"1-46","source":"Crossref","is-referenced-by-count":11,"title":["Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics"],"prefix":"10.1137","volume":"53","author":[{"given":"David","family":"Gamarnik","sequence":"first","affiliation":[{"name":"Sloan School of Management and Operations Research Center, MIT, Boston, MA 02140 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aukosh","family":"Jagannath","sequence":"additional","affiliation":[{"name":"Department of Statistics and Actuarial Science, Department of Applied Mathematics, and Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander S.","family":"Wein","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California, Davis, CA 95616 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,2,13]]},"reference":[{"key":"ref2","volume-title":"The Probabilistic Method","author":"Alon N.","year":"2004"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21422"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2018.03.028"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008774"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-005-0491-y"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOP1415"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-019-03649-4"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-018-3152-6"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/ab7b1f"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1142\/9789812819437_0006"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOP1291"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-016-2808-3"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/16M1084158"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01312184"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-44835-8_7"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.71.173"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-006-9228-2"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s11511-017-0145-9"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0909892106"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1214\/21-AOP1519"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90149-C"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2108492118"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1448"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1114"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1137\/140989728"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1214\/18-AIHP897"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-002-0699-y"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-40908-3_5"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-27-237"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/038"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1063\/1.5094173"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.4171\/AIHPD\/97"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-017-2864-3"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511526169"},{"key":"ref54","first-page":"1","volume-title":"Algorithms and Complexity","author":"Karp R. M.","year":"1976"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.02.006"},{"key":"ref57","volume-title":"Classics in Mathematics","author":"Ledoux M.","year":"2011","edition":"1991"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1137\/14099721X"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1051\/jphys:01984004505084300"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-6289-7"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1094"},{"key":"ref68","first-page":"2897","volume-title":"Advances in Neural Information Processing Systems","author":"Richard E.","year":"2014"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1214\/22-AOS2179"},{"key":"ref73","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.5802\/crmath.240","volume":"359","author":"Sellke M.","year":"2021","journal-title":"C. R. Math. Acad. Sci. Paris"},{"key":"ref76","volume-title":"Introduction to the Theory of Computability","author":"Sipser M.","year":"1997"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21922"},{"key":"ref78","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-016-0724-2"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/140"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1090\/cln\/027"},{"key":"ref82","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref83","doi-asserted-by":"publisher","DOI":"10.4171\/msl\/25"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T04:50:31Z","timestamp":1731300631000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M150263X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,13]]},"references-count":57,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1137\/22M150263X"],"URL":"https:\/\/doi.org\/10.1137\/22m150263x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,13]]}}}