{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T04:22:31Z","timestamp":1775794951805,"version":"3.50.1"},"reference-count":25,"publisher":"IEEE Computer. Soc","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1109\/sfcs.2003.1238204","type":"proceedings-article","created":{"date-parts":[[2004,2,3]],"date-time":"2004-02-03T19:24:01Z","timestamp":1075836241000},"page":"298-307","source":"Crossref","is-referenced-by-count":109,"title":["More on average case vs approximation complexity"],"prefix":"10.1109","author":[{"given":"M.","family":"Alekhnovich","sequence":"first","affiliation":[]}],"member":"263","reference":[{"key":"19","first-page":"213","article-title":"Computation of rigidity of order n\/r for one simple matrix","volume":"32","author":"pudlak","year":"1991","journal-title":"Commentat Math Univ Carol"},{"key":"17","first-page":"114","article-title":"A public-key cryptosystem based on algebraic coding theory","author":"mceliece","year":"1978"},{"key":"18","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"15","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1786"},{"key":"16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02128669"},{"key":"13","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02311250"},{"key":"11","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276704"},{"key":"12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122554"},{"key":"21","article-title":"On rigid matrices","author":"razborov","year":"1989"},{"key":"20","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(00)00201-8"},{"key":"22","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1494"},{"key":"23","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00190-7"},{"key":"24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-81955-1_28"},{"key":"25","first-page":"162","article-title":"Graph-theoretic arguments in low-level complexity","author":"valiant","year":"1977","journal-title":"Proc Symp Math Foundations of Computer Science"},{"key":"3","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258604"},{"key":"2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"10","doi-asserted-by":"publisher","DOI":"10.1109\/49.17716"},{"key":"1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892064"},{"key":"7","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"6","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780594"},{"key":"5","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"4","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303207"},{"key":"8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20213"}],"event":{"name":"44th Annual IEEE Symposium on Foundations of Computer Science - FOCS 2003","location":"Cambridge, MA, USA","acronym":"SFCS-03"},"container-title":["44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings."],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx5\/8767\/27770\/01238204.pdf?arnumber=1238204","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,3,13]],"date-time":"2017-03-13T17:27:03Z","timestamp":1489426023000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/1238204\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":25,"URL":"https:\/\/doi.org\/10.1109\/sfcs.2003.1238204","relation":{},"subject":[]}}