{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:15Z","timestamp":1750307175423,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,3,7]],"date-time":"2012-03-07T00:00:00Z","timestamp":1331078400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2012,3,7]]},"abstract":"<jats:p>In a projection PCP, also known as Label-Cover, the verifier makes two queries to the proof, and the answer to the first query determines at most one satisfying answer to the second query. Projection PCPs with low error probability are the basis of most NP-hardness of approximation results known today. In this essay we outline a construction of a projection PCP with low error and low blow-up. This yields sharp approximation thresholds and tight time lower bounds for approximation of a variety of problems, under an assumption on the time required for solving certain NP-hard problems exactly. The approach of the construction is algebraic, and it includes components such as low error, randomness-efficient low degree testing and composition of projection PCPs.<\/jats:p>","DOI":"10.1145\/2160649.2160669","type":"journal-article","created":{"date-parts":[[2012,3,13]],"date-time":"2012-03-13T12:29:14Z","timestamp":1331641754000},"page":"62-81","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest column"],"prefix":"10.1145","volume":"43","author":[{"given":"Dana","family":"Moshkovitz","sequence":"first","affiliation":[{"name":"MIT"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,3,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"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\/167088.167174"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050646445"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-011-0014-4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225183"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1067309.1067318"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89518"},{"key":"e_1_2_1_17_1","unstructured":"D. Moshkovitz. Lecture notes in probabilistically checkable proofs MIT. http:\/\/people.csail.mit.edu\/dmoshkov\/courses\/pcp-mit\/index.html.  D. Moshkovitz. Lecture notes in probabilistically checkable proofs MIT. http:\/\/people.csail.mit.edu\/dmoshkov\/courses\/pcp-mit\/index.html."},{"key":"e_1_2_1_18_1","unstructured":"D. Moshkovitz. An alternative proof of the Schwartz-Zippel lemma. Technical report ECCC TR10-096 2010.  D. Moshkovitz. An alternative proof of the Schwartz-Zippel lemma. Technical report ECCC TR10-096 2010."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/060656838"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754402"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1960.1057584"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_28_1","unstructured":"M. Sudan. Lecture notes in essential coding theory MIT. http:\/\/people.csail.mit.edu\/madhu\/coding\/course.html  M. Sudan. Lecture notes in essential coding theory MIT. http:\/\/people.csail.mit.edu\/madhu\/coding\/course.html"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19821090103"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160649.2160669","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2160649.2160669","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:51Z","timestamp":1750240491000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2160649.2160669"}},"subtitle":["algebraic construction of projection PCPs"],"short-title":[],"issued":{"date-parts":[[2012,3,7]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,3,7]]}},"alternative-id":["10.1145\/2160649.2160669"],"URL":"https:\/\/doi.org\/10.1145\/2160649.2160669","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2012,3,7]]},"assertion":[{"value":"2012-03-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}