{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T04:51:01Z","timestamp":1767847861230,"version":"3.49.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0343672"],"award-info":[{"award-number":["CCF-0343672"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2009,9]]},"abstract":"<jats:p>\n            A classic result due to H\u00e5stad established that for every constant\n            <jats:italic>\u03b5<\/jats:italic>\n            \u2009&gt;\u20090, given an overdetermined system of linear equations over a finite field F\n            <jats:sub>q<\/jats:sub>\n            where each equation depends on exactly 3 variables and at least a fraction (1\u2009\u2212\u2009\n            <jats:italic>\u03b5<\/jats:italic>\n            ) of the equations can be satisfied, it is NP-hard to satisfy even a fraction (1\/\n            <jats:italic>q<\/jats:italic>\n            \u2009+\u2009\u03b5) of the equations.\n          <\/jats:p>\n          <jats:p>\n            In this work, we prove the analog of H\u00e5stad\u2019s result for equations over the integers (as well as the reals). Formally, we prove that for every\n            <jats:italic>\u03b5<\/jats:italic>\n            ,\n            <jats:italic>\u03b4<\/jats:italic>\n            \u2009&gt;\u20090, given a system of linear equations with integer coefficients where each equation is on 3 variables, it is NP-hard to distinguish between the following two cases: (i) there is an assignment of integer values to the variables that satisfies at least a fraction (1\u2009\u2212\u2009\n            <jats:italic>\u03b5<\/jats:italic>\n            ) of the equations, and (ii) no assignment even of real values to the variables satisfies more than a fraction\n            <jats:italic>\u03b4<\/jats:italic>\n            of the equations.\n          <\/jats:p>","DOI":"10.1145\/1595391.1595393","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T14:56:36Z","timestamp":1259592996000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Hardness of Solving Sparse Overdetermined Linear Systems"],"prefix":"10.1145","volume":"1","author":[{"given":"Venkatesan","family":"Guruswami","sequence":"first","affiliation":[{"name":"University of Washington"}]},{"given":"Prasad","family":"Raghavendra","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"320","published-online":{"date-parts":[[2009,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00115-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1472"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.08.012"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.33"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00020"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067318"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595391.1595393","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1595391.1595393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:03Z","timestamp":1750253403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1595391.1595393"}},"subtitle":["A 3-Query PCP over Integers"],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1595391.1595393"],"URL":"https:\/\/doi.org\/10.1145\/1595391.1595393","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}