{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:46:02Z","timestamp":1781077562436,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2007,6,11]],"date-time":"2007-06-11T00:00:00Z","timestamp":1181520000000},"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":[[2007,6,11]]},"DOI":"10.1145\/1250790.1250864","type":"proceedings-article","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T16:07:37Z","timestamp":1189786057000},"page":"506-515","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":70,"title":["Low-degree tests at large distances"],"prefix":"10.1145","author":[{"given":"Alex","family":"Samorodnitsky","sequence":"first","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"188","article-title":"Ron, Testing low-degree polynomials over GF(2)","author":"Alon N.","year":"2003","unstructured":"N. Alon , T. Kaufman , M. Krivelevich , S. Litsyn , D . Ron, Testing low-degree polynomials over GF(2) , RANDOM-APPROX 2003 , pp. 188 -- 199 . N. Alon, T. Kaufman, M. Krivelevich, S. Litsyn, D. Ron, Testing low-degree polynomials over GF(2), RANDOM-APPROX 2003, pp. 188--199.","journal-title":"RANDOM-APPROX"},{"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","first-page":"42","article-title":"Sudan Linearity testing in characteristic 2","author":"Bellare M.","year":"1996","unstructured":"M. Bellare , D. Coppersmith , J. Hastad , M. Kiwi , M . Sudan Linearity testing in characteristic 2 , IEEE Trans. Inform. Theory , vol. I T- 42 , 6, 1996 , 1782--1795. M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi, M. Sudan Linearity testing in characteristic 2, IEEE Trans. Inform. Theory, vol. IT-42, 6, 1996, 1782--1795.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"e_1_3_2_1_5_1","volume-title":"Personal communication to the authors of BLR","author":"Ben-Or M.","year":"1989","unstructured":"M. Ben-Or , D. Coppersmith , Personal communication to the authors of BLR , 1989 . M. Ben-Or, D. Coppersmith, Personal communication to the authors of BLR, 1989."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132547"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00535-2"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652169"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_3_2_1_12_1","unstructured":"B. Green Montreal notes on quadratic Fourier analysis preprint Mathematics ArXiv CA\/0604089.  B. Green Montreal notes on quadratic Fourier analysis preprint Mathematics ArXiv CA\/0604089."},{"key":"e_1_3_2_1_13_1","unstructured":"B. Green and T. Tao. The primes contain arbitrarily long arithmetic progressions Annals of Mathematics to appear.  B. Green and T. Tao. The primes contain arbitrarily long arithmetic progressions Annals of Mathematics to appear."},{"key":"e_1_3_2_1_14_1","volume-title":"Proc. Edin. Math. Soc.","author":"Green B.","unstructured":"B. Green , T. Tao, An inverse theorem for the Gowers U<sup>3<\/sup> norm , Proc. Edin. Math. Soc. , to appear. B. Green, T. Tao, An inverse theorem for the Gowers U<sup>3<\/sup> norm, Proc. Edin. Math. Soc., to appear."},{"key":"e_1_3_2_1_15_1","volume-title":"ICALP","author":"Hast G.","year":"2005","unstructured":"G. Hast , Approximating Max kCSP - outperforming a random assignment by almost a linear factor , ICALP 2005 , to appear. G. Hast, Approximating Max kCSP - outperforming a random assignment by almost a linear factor, ICALP 2005, to appear."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.161.397"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_2_1_19_1","volume-title":"The Theory of Error Correcting Codes","author":"MacWilliams J.","year":"1977","unstructured":"J. MacWilliams and N. J. A. Sloane , The Theory of Error Correcting Codes , Amsterdam , North-Holland , 1977 . J. MacWilliams and N. J. A. Sloane, The Theory of Error Correcting Codes, Amsterdam, North-Holland, 1977."},{"key":"e_1_3_2_1_20_1","volume-title":"Matroid Theory","author":"Oxley J. G.","year":"1992","unstructured":"J. G. Oxley , Matroid Theory , New York , Oxford University Press , 1992 . J. G. Oxley, Matroid Theory, New York, Oxford University Press, 1992."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1954.1057465"},{"key":"e_1_3_2_1_22_1","first-page":"323","volume-title":"Asterisque 258, 199","author":"Ruzsa I. Z.","unstructured":"I. Z. Ruzsa , An analog of Freiman's theorem in groups , Asterisque 258, 199 , pp. 323 -- 326 . I. Z. Ruzsa, An analog of Freiman's theorem in groups, Asterisque 258, 199, pp. 323--326."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335329"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132519"},{"key":"e_1_3_2_1_25_1","first-page":"25","volume-title":"IFIP TCS","author":"Sudan M.","year":"2000","unstructured":"M. Sudan , List decoding : algorithms and applications , IFIP TCS 2000 , pp. 25 -- 41 . M. Sudan, List decoding: algorithms and applications, IFIP TCS 2000, pp. 25--41."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009209"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276769"},{"key":"e_1_3_2_1_28_1","first-page":"53","article-title":"Universal characteristic factors and Furstenberg averages","volume":"20","author":"Ziegler T.","year":"2007","unstructured":"T. Ziegler , Universal characteristic factors and Furstenberg averages , Journal of AMS 20 , 2007 , pp. 53 -- 97 . T. Ziegler, Universal characteristic factors and Furstenberg averages, Journal of AMS 20, 2007, pp. 53--97.","journal-title":"Journal of AMS"}],"event":{"name":"STOC07: Symposium on Theory of Computing","location":"San Diego California USA","acronym":"STOC07","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-ninth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1250790.1250864","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1250790.1250864","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:52:21Z","timestamp":1750258341000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1250790.1250864"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,11]]},"references-count":28,"alternative-id":["10.1145\/1250790.1250864","10.1145\/1250790"],"URL":"https:\/\/doi.org\/10.1145\/1250790.1250864","relation":{},"subject":[],"published":{"date-parts":[[2007,6,11]]},"assertion":[{"value":"2007-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}