{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T05:00:13Z","timestamp":1773378013432,"version":"3.50.1"},"reference-count":51,"publisher":"IEEE","license":[{"start":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T00:00:00Z","timestamp":1656201600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T00:00:00Z","timestamp":1656201600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,26]]},"DOI":"10.1109\/isit50566.2022.9834647","type":"proceedings-article","created":{"date-parts":[[2022,8,3]],"date-time":"2022-08-03T15:34:22Z","timestamp":1659540862000},"page":"778-783","source":"Crossref","is-referenced-by-count":1,"title":["The Random Number Partitioning Problem: Overlap Gap Property and Algorithmic Barriers"],"prefix":"10.1109","author":[{"given":"David","family":"Gamarnik","sequence":"first","affiliation":[{"name":"MIT"}]},{"given":"Eren C.","family":"K\u00edz\u00edlda\u011f","sequence":"additional","affiliation":[{"name":"MIT"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.4171\/PM\/2014"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1080\/00018732.2016.1211393"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.72"},{"key":"ref32","first-page":"956","article-title":"Tensor principal component analysis via sum-of-square proofs","author":"hopkins","year":"2015","journal-title":"Conference on Learning Theory"},{"key":"ref31","article-title":"Computational lower bounds for sparse pca","author":"berthet","year":"2013"},{"key":"ref30","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS54457.2022.00061","article-title":"Algorithms and barriers in the symmetric binary perceptron model","author":"gamarnik","year":"2022"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1214\/20-AAP1625"},{"key":"ref36","article-title":"Algorithms and algorithmic barriers in high-dimensional statistics and random combinatorial structures","author":"k?z?lda?","year":"2022","journal-title":"Ph D Dissertation"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1137\/17M1138236"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1214\/18-AOP1291"},{"key":"ref27","article-title":"Optimal low-degree hardness of maximum independent set","author":"wein","year":"2020"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOP1448"},{"key":"ref2","article-title":"Balancing covariates in randomized experiments using the gram-schmidt walk","author":"harshaw","year":"2019"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/asz026"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2108492118"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1287\/moor.21.1.85"},{"key":"ref21","author":"karmarkar","year":"1982","journal-title":"The differencing method of set partitioning"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.11"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1114"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20550"},{"key":"ref50","first-page":"2052","article-title":"Algorithmic thresholds for tensor pca","volume":"48","author":"arous","year":"2020","journal-title":"Annals of Probability"},{"key":"ref51","article-title":"The overlap gap property in principal submatrix recovery","author":"gamarnik","year":"2019"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.2307\/2000258"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"ref40","article-title":"Reducibility and computational lower bounds for problems with planted sparse structure","author":"brennan","year":"2018"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/130929400"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/141000282"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.2307\/3214002"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-009-0068-z"},{"key":"ref16","first-page":"3455","article-title":"Balancing gaussian vectors in high dimension","author":"turner","year":"2020","journal-title":"Conference on Learning Theory"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554838"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8121\/ab227a"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451119"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055927"},{"key":"ref3","article-title":"Algorithmic obstructions in the random number partitioning problem","author":"gamarnik","year":"2021"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/0221007"},{"key":"ref5","author":"coffman","year":"1991","journal-title":"Probabilistic Analysis of Packing and Partitioning Algorithms"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10004"},{"key":"ref7","author":"garey","year":"1990","journal-title":"Computers and Intractability A Guide to the Theory of NP-Completeness"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/140989728"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20255"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(90)90149-C"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132537"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1094"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00021"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.16"},{"key":"ref41","article-title":"Optimal average-case reductions to sparse pca: From weak assumptions to strong hardness","author":"brennan","year":"2019"},{"key":"ref44","article-title":"Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio","author":"kunisky","year":"2019"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/3046674"}],"event":{"name":"2022 IEEE International Symposium on Information Theory (ISIT)","location":"Espoo, Finland","start":{"date-parts":[[2022,6,26]]},"end":{"date-parts":[[2022,7,1]]}},"container-title":["2022 IEEE International Symposium on Information Theory (ISIT)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/9834325\/9834269\/09834647.pdf?arnumber=9834647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T20:35:54Z","timestamp":1773347754000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9834647\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,26]]},"references-count":51,"URL":"https:\/\/doi.org\/10.1109\/isit50566.2022.9834647","relation":{},"subject":[],"published":{"date-parts":[[2022,6,26]]}}}