{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,4]],"date-time":"2025-10-04T00:42:44Z","timestamp":1759538564837,"version":"build-2065373602"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2025,8,31]]},"DOI":"10.1137\/20m1322297","type":"journal-article","created":{"date-parts":[[2022,3,7]],"date-time":"2022-03-07T11:23:24Z","timestamp":1646652204000},"page":"FOCS19-102-FOCS19-134","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Construction of Rigid Matrices Using an NP Oracle"],"prefix":"10.1137","volume":"54","author":[{"given":"Josh","family":"Alman","sequence":"first","affiliation":[{"name":"Columbia University, New York, NY 10027 USA."}]},{"given":"Lijie","family":"Chen","sequence":"additional","affiliation":[{"name":"CSAIL, Massachusetts Institute of Technology, Cambridge, MA 02139 USA."}]}],"member":"351","published-online":{"date-parts":[[2022,3,7]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2004.160.781"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.18"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1137\/0219074"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263423"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/0211037"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303207"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0104-9"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0166-6"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-003-0178-7"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00024-7"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700389652"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00008-6"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1786"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1561\/0400000011"},{"key":"ref36","first-page":"1171","volume-title":"Dokl. Akad. Nauk SSSR","volume":"111","author":"Lupanov O. B.","year":"1956"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2732"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0197-7"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-020-00199-3"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215351"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480197329508"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00190-7"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/BF01270384"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"ref49","first-page":"100","volume":"23","author":"Tamaki S.","year":"2016","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/10080703X"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1145\/2559903"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0021-5"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90015-4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T16:16:09Z","timestamp":1759508169000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1322297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,7]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,31]]}},"alternative-id":["10.1137\/20M1322297"],"URL":"https:\/\/doi.org\/10.1137\/20m1322297","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"type":"print","value":"0097-5397"},{"type":"electronic","value":"1095-7111"}],"subject":[],"published":{"date-parts":[[2022,3,7]]}}}