{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:16:22Z","timestamp":1774941382793,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2004,6,13]],"date-time":"2004-06-13T00:00:00Z","timestamp":1087084800000},"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":[],"published-print":{"date-parts":[[2004,6,13]]},"DOI":"10.1145\/1007352.1007421","type":"proceedings-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T15:55:38Z","timestamp":1090338938000},"page":"427-435","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Derandomizing homomorphism testing in general groups"],"prefix":"10.1145","author":[{"given":"Amir","family":"Shpilka","sequence":"first","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]},{"given":"Avi","family":"Wigderson","sequence":"additional","affiliation":[{"name":"Institute for Advanced Study, Princeton, NJ"}]}],"member":"320","published-online":{"date-parts":[[2004,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"e_1_3_2_1_2_1","first-page":"3","article-title":"Simple Constructions of Almost k-wise Independent Random Variables","volume":"3","author":"Alon N.","year":"1992","journal-title":"Journal of Random Structures and Algorithms"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(95)00032-8"},{"key":"e_1_3_2_1_4_1","first-page":"320","volume-title":"25th Annual Symposium on Foundations of Computer Science","author":"Alon N.","year":"1984"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050203"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195129"},{"key":"e_1_3_2_1_9_1","volume-title":"Manuscript","author":"Ben-Or M.","year":"2003"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796263"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780631"},{"key":"e_1_3_2_1_13_1","first-page":"187","volume-title":"Journal of the AMS","volume":"1989","author":"Chung F. R. K."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/129712.129714"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.16"},{"key":"e_1_3_2_1_16_1","unstructured":"O. Goldreich. Private Communication June 2002.  O. Goldreich. Private Communication June 2002."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"O. Goldreich. Combinatorial Property Testing. DIMACS series in Discrete Mathematics and Theoretical Computer Science pages 45--59 Vol. 43 1998.  O. Goldreich. Combinatorial Property Testing. DIMACS series in Discrete Mathematics and Theoretical Computer Science pages 45--59 Vol. 43 1998.","DOI":"10.1090\/dimacs\/043\/04"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10068"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_22_1","first-page":"197","article-title":"An Estimate for Character Sums","volume":"2","author":"Katz N. M.","year":"1963","journal-title":"J. AMS"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"A. Lubotzky. Discrete Groups Expanding Graphs and Invariant Measures. Progress in Math. 125 Birkhauser Verlag Basel 1994.  A. Lubotzky. Discrete Groups Expanding Graphs and Invariant Measures. Progress in Math. 125 Birkhauser Verlag Basel 1994.","DOI":"10.1007\/978-3-0346-0332-4_10"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"A. Lubotzky R. Phillips P. Sarnak. Ramanujan graphs Combinatorica pages 261--277 Vol. 8 1988.  A. Lubotzky R. Phillips P. Sarnak. Ramanujan graphs Combinatorica pages 261--277 Vol. 8 1988.","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_25_1","first-page":"71","volume-title":"Problemy Peredachi Informatsii","author":"Margulis G. A.","year":"1973"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1994.1054"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100244"},{"key":"e_1_3_2_1_28_1","unstructured":"D. Ron. Property testing (a tutorial). Handbook of Randomized Computing (S. Rajasekaran P. M. Pardalos J. H. Reif and J. D. P. Rolim editors) Kluwer Press (2001).  D. Ron. Property testing (a tutorial). Handbook of Randomized Computing (S. Rajasekaran P. M. Pardalos J. H. Reif and J. D. P. Rolim editors) Kluwer Press (2001)."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_3_2_1_32_1","first-page":"287","volume-title":"SIAM Journal on on Algebraic Discrete Methods","volume":"1984","author":"Tanner R. M."}],"event":{"name":"STOC04: Symposium of Theory of Computing 2004","location":"Chicago IL USA","acronym":"STOC04","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007421","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1007352.1007421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:56Z","timestamp":1750267436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007421"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6,13]]},"references-count":31,"alternative-id":["10.1145\/1007352.1007421","10.1145\/1007352"],"URL":"https:\/\/doi.org\/10.1145\/1007352.1007421","relation":{},"subject":[],"published":{"date-parts":[[2004,6,13]]},"assertion":[{"value":"2004-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}