{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:24:16Z","timestamp":1761805456687},"reference-count":24,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"Jacobs Family Presidential Fellowship"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1451191","CCF-1523816"],"award-info":[{"award-number":["DMS-1451191","CCF-1523816"]}],"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-1412958"],"award-info":[{"award-number":["CCF-1412958"]}],"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":[[2020,1]]},"DOI":"10.1137\/19m124647x","type":"journal-article","created":{"date-parts":[[2020,5,13]],"date-time":"2020-05-13T16:56:15Z","timestamp":1589388975000},"page":"465-496","source":"Crossref","is-referenced-by-count":3,"title":["Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs"],"prefix":"10.1137","volume":"49","author":[{"given":"Zeev","family":"Dvir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sivakanth","family":"Gopi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuzhou","family":"Gu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"351","published-online":{"date-parts":[[2020,5,13]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701389944"},{"key":"atypb2","first-page":"190","author":"Alekhnovich M.","year":"2001","journal-title":"IEEE"},{"key":"atypb3","first-page":"638","author":"Bhattacharyya A.","year":"2011","journal-title":"IEEE"},{"key":"atypb5","first-page":"519","author":"Barak B.","year":"2011","journal-title":"ACM"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"atypb7","first-page":"1","volume":"2017","author":"Bhattacharyya A.","year":"2017","journal-title":"APPROX\/RANDOM"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-014-1515-0"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375835"},{"key":"atypb12","first-page":"507","author":"Dinur I.","year":"2011","journal-title":"Algorithms and Techniques Springer"},{"key":"atypb13","first-page":"784","author":"Dvir Z.","year":"2014","journal-title":"ACM"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1561\/0400000056"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772959"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.03.010"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0017-0"},{"key":"atypb21","first-page":"439","volume":"43","author":"Hoory S.","year":"2006","journal-title":"S.)"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187687"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1145\/3051093"},{"key":"atypb26","first-page":"80","year":"2000","journal-title":"ACM"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"atypb28","first-page":"2007","author":"Matus F.","year":"2007","journal-title":"Proceedings of the IEEE International Symposium on Information Theory"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00208-8"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/18.681320"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M124647X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T15:31:59Z","timestamp":1590161519000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M124647X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M124647X"],"URL":"https:\/\/doi.org\/10.1137\/19m124647x","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}