{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:58:55Z","timestamp":1778065135867,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2005,5,22]]},"DOI":"10.1145\/1060590.1060631","type":"proceedings-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:31:47Z","timestamp":1123057907000},"page":"266-275","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Simple PCPs with poly-log rate and query complexity"],"prefix":"10.1145","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Israel Institute of Technology, Haifa, Israel and Toyota Technological Institute, Chicago, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,5,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/971651.971653"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875552"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007361"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Ben-Sasson E. and Sudan M. Simple PCPs with Poly-log Rate and Query Complexity. Preliminary version at http:\/\/eccc.uni-trier.de\/eccc-reports\/2004\/TR04-060\/index.html  Ben-Sasson E. and Sudan M. Simple PCPs with Poly-log Rate and Query Complexity. Preliminary version at http:\/\/eccc.uni-trier.de\/eccc-reports\/2004\/TR04-060\/index.html","DOI":"10.1145\/1060590.1060631"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276741"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301265"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.16"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_3_2_1_16_1","first-page":"57","volume-title":"Low-degree tests.Proceedings of the 5th Annual ACM-SIAM Symposium on Dis rete Algorithms","author":"Friedl Z.","year":"1994","unstructured":"K. Friedl , Z. Hatsagi ,and A. Shen . Low-degree tests.Proceedings of the 5th Annual ACM-SIAM Symposium on Dis rete Algorithms , pages 57 -- 64 , 1994 . K. Friedl,Z. Hatsagi,and A. Shen. Low-degree tests.Proceedings of the 5th Annual ACM-SIAM Symposium on Dis rete Algorithms, pages 57--64,1994."},{"key":"e_1_3_2_1_17_1","volume-title":"Tech.Rep. TR97-020,Electronic Colloquium on Computational Complexity","author":"Goldreich O.","year":"1997","unstructured":"Goldreich , O. A sample o samplers -a computational perspective on sampling . Tech.Rep. TR97-020,Electronic Colloquium on Computational Complexity , 1997 . O. Goldreich Goldreich, O. A sample o samplers -a computational perspective on sampling. Tech.Rep. TR97-020,Electronic Colloquium on Computational Complexity, 1997. O. Goldreich"},{"key":"e_1_3_2_1_18_1","first-page":"13","volume-title":"Pro .43 rd IEEE Symp.on Foundations of Comp.Science (Vancouver,Canada,16 -19 Nov.2002)","author":"Goldreich O.","year":"2002","unstructured":"Goldreich , O. , and Sudan , M . Locally testable codes and PCPs of almost linear length . In Pro .43 rd IEEE Symp.on Foundations of Comp.Science (Vancouver,Canada,16 -19 Nov.2002) , pp. 13 -- 22 . ( See ECC Report TR 02-050, 2002 ). Goldreich, O., and Sudan, M. Locally testable codes and PCPs of almost linear length. In Pro .43 rd IEEE Symp.on Foundations of Comp.Science (Vancouver,Canada,16 -19 Nov.2002), pp.13--22. (See ECC Report TR02-050,2002)."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796391"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/646515.695972"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129782"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172769","volume-title":"H Introduction to finite fields and their appliations","author":"Lidl R.","year":"1994","unstructured":"Lidl , R. and Niederreiter , H Introduction to finite fields and their appliations . Cambridge University Press, Cambridge , UK. Revised edition, 1994 . Lidl, R. and Niederreiter, H Introduction to finite fields and their appliations. Cambridge University Press, Cambridge, UK. Revised edition, 1994."},{"issue":"57","key":"e_1_3_2_1_24_1","first-page":"139","volume":"15","author":"Linnik U. V.","year":"1944","unstructured":"Linnik , U. V. On the Least Prime in an Arithmetic Progression.I.The Basic Theorem.In Mat.Sbornik N.S . 15 ( 57 ), 139 -- 178 , 1944 . Linnik, U. V. On the Least Prime in an Arithmetic Progression.I.The Basic Theorem.In Mat.Sbornik N.S.15 (57), 139--178, 1944.","journal-title":"Arithmetic Progression.I.The Basic Theorem.In Mat.Sbornik N.S"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89518"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795284959"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195132"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_3_2_1_30_1","volume-title":"MIT","author":"Spielman D. A.","year":"1995","unstructured":"Spielman , D. A. Computationally Efficient Error-Correcting Codes and Holographic Proofs Ph. D. Thesis , MIT , Cambridge, MA , 1995 . Spielman, D. A. Computationally Efficient Error-Correcting Codes and Holographic Proofs Ph. D. Thesis, MIT, Cambridge, MA, 1995."}],"event":{"name":"STOC05: Symposium on Theory of Computing","location":"Baltimore MD USA","acronym":"STOC05","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-seventh annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1060590.1060631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T08:25:23Z","timestamp":1673166323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1060590.1060631"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,22]]},"references-count":30,"alternative-id":["10.1145\/1060590.1060631","10.1145\/1060590"],"URL":"https:\/\/doi.org\/10.1145\/1060590.1060631","relation":{},"subject":[],"published":{"date-parts":[[2005,5,22]]},"assertion":[{"value":"2005-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}