{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:23:27Z","timestamp":1758824607943,"version":"3.41.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,12,10]],"date-time":"2013-12-10T00:00:00Z","timestamp":1386633600000},"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":[[2013,12,10]]},"abstract":"<jats:p>An affine-invariant property over a finite field is a property of functions over Fn\/p that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has seen rapid progress in characterizing the affine-invariant properties which are testable with a constant number of queries. We survey the current state of this project.<\/jats:p>","DOI":"10.1145\/2556663.2556678","type":"journal-article","created":{"date-parts":[[2013,12,17]],"date-time":"2013-12-17T13:36:15Z","timestamp":1387287375000},"page":"53-72","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Guest column"],"prefix":"10.1145","volume":"44","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132555"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.856958"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/06064888X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132556"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2011.v007a006"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488662"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.97"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.83"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000363"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.53"},{"key":"e_1_2_1_15_1","volume-title":"Manuscript","author":"Bhattacharyya Arnab","year":"2013","unstructured":"Arnab Bhattacharyya , Pooya Hatami , and Madhur Tulsiani . Algorithmic regularity for polynomials and applications . Manuscript , October 2013 . 15 Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani. Algorithmic regularity for polynomials and applications. Manuscript, October 2013. 15"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0051-1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873610"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789812562494_0014"},{"key":"e_1_2_1_22_1","volume-title":"August","author":"Fu Hu","year":"2013","unstructured":"Hu Fu and Robert Kleinberg . Improved lower bounds for testing triangle-freeness in boolean functions via fast matrix multiplication. Technical report , August 2013 . http:\/\/arxiv.org\/abs\/1308.1643. 16 Hu Fu and Robert Kleinberg. Improved lower bounds for testing triangle-freeness in boolean functions via fast matrix multiplication. Technical report, August 2013. http:\/\/arxiv.org\/abs\/1308.1643. 16"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/060652324"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_25_1","series-title":"Lecture Notes in Comput","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/978-3-642-22935-0_49","volume-title":"Approximation, randomization, and combinatorial optimization","author":"Goldreich Oded","year":"2011","unstructured":"Oded Goldreich and Tali Kaufman . Proximity oblivious testing and the role of invariances . In Approximation, randomization, and combinatorial optimization , volume 6845 of Lecture Notes in Comput . Sci., pages 579 -- 592 . Springer , Heidelberg, 2011 . 4 Oded Goldreich and Tali Kaufman. Proximity oblivious testing and the role of invariances. In Approximation, randomization, and combinatorial optimization, volume 6845 of Lecture Notes in Comput. Sci., pages 579--592. Springer, Heidelberg, 2011. 4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73010"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.71"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_42"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/100789646"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-005-0509-8"},{"key":"e_1_2_1_32_1","volume-title":"April","author":"Green Ben","year":"2007","unstructured":"Ben Green . Montr\u00e9al notes on quadratic Fourier analysis. Technical report , April 2007 . http:\/\/arxiv.org\/abs\/math\/0604089. 12 Ben Green. Montr\u00e9al notes on quadratic Fourier analysis. Technical report, April 2007. http:\/\/arxiv.org\/abs\/math\/0604089. 12"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_48"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10078"},{"issue":"2","key":"e_1_2_1_35_1","first-page":"1","article-title":"The distribution of polynomials over finite fields, with applications to the Gowers norms","volume":"4","author":"Green Ben","year":"2009","unstructured":"Ben Green and Terence Tao . The distribution of polynomials over finite fields, with applications to the Gowers norms . Contrib. Discrete Math. , 4 ( 2 ): 1 -- 36 , 2009 . 14 Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms. Contrib. Discrete Math., 4(2):1--36, 2009. 14","journal-title":"Contrib. Discrete Math."},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Ben\n      Green\n     and \n      Terence\n      Tao\n    .\n  An Irregular Mind: Szemer\u00e9di is 70 volume \n  21\n   of \n  Bolyai Society Mathematical Studies chapter An arithmetic regularity lemma associated counting lemma and applications pages \n  261\n  --\n  334\n  . \n  Springer 2010\n  . 13  Ben Green and Terence Tao. An Irregular Mind: Szemer\u00e9di is 70 volume 21 of Bolyai Society Mathematical Studies chapter An arithmetic regularity lemma associated counting lemma and applications pages 261--334. Springer 2010. 13","DOI":"10.1007\/978-3-642-14444-8_7"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2010.171.1753"},{"key":"e_1_2_1_38_1","volume-title":"August","author":"Hatami Hamed","year":"2013","unstructured":"Hamed Hatami , Pooya Hatami , and James Hirst . Limits of boolean functions on Fn\/p. Technical report , August 2013 . http:\/\/arxiv.org\/abs\/1308.4108. 17 Hamed Hatami, Pooya Hatami, and James Hirst. Limits of boolean functions on Fn\/p. Technical report, August 2013. http:\/\/arxiv.org\/abs\/1308.4108. 17"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993662"},{"key":"e_1_2_1_40_1","volume-title":"June","author":"Hatami Hamed","year":"2013","unstructured":"Hamed Hatami and Shachar Lovett . Estimating the distance from testable affineinvariant properties. Technical report , June 2013 . http:\/\/arxiv.org\/abs\/1306. 0649v1, to appear in FOCS '13. 8, 9 Hamed Hatami and Shachar Lovett. Estimating the distance from testable affineinvariant properties. Technical report, June 2013. http:\/\/arxiv.org\/abs\/1306. 0649v1, to appear in FOCS '13. 8, 9"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.17"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374434"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2008.12.003"},{"key":"e_1_2_1_44_1","first-page":"1","volume-title":"Israel J. Math","author":"Kr\u00e1l Daniel","year":"2012","unstructured":"Daniel Kr\u00e1l , Oriol Serra , and Llu\u00eds Vena . A removal lemma for systems of linear equations over finite fields . Israel J. Math , pages 1 -- 15 , 2012 . 9 Daniel Kr\u00e1l, Oriol Serra, and Llu\u00eds Vena. A removal lemma for systems of linear equations over finite fields. Israel J. Math, pages 1--15, 2012. 9"},{"key":"e_1_2_1_45_1","volume-title":"Proc. DIMACS workshop on Distributed computing and Cryptography","author":"Lipton Richard","year":"1989","unstructured":"Richard Lipton . New directions in testing . In Proc. DIMACS workshop on Distributed computing and Cryptography , 1989 . 5 Richard Lipton. New directions in testing. In Proc. DIMACS workshop on Distributed computing and Cryptography, 1989. 5"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374454"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:2"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000029"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20017"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2320-x"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791075"},{"key":"e_1_2_1_53_1","first-page":"1095","volume-title":"Proceedings of International Congress of Mathematicians 2006","volume":"3","author":"Rubinfeld Ronitt","year":"2006","unstructured":"Ronitt Rubinfeld . Sublinear time algorithms . In Proceedings of International Congress of Mathematicians 2006 , volume 3 , pages 1095 -- 1110 , 2006 . 3 Ronitt Rubinfeld. Sublinear time algorithms. In Proceedings of International Congress of Mathematicians 2006, volume 3, pages 1095--1110, 2006. 3"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536438"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1730"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/1959045.1959062"},{"key":"e_1_2_1_58_1","first-page":"399","volume-title":"Proc. Colloque Internationaux CNRS 260 -- Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes","author":"Szemer\u00e9di Endre","year":"1978","unstructured":"Endre Szemer\u00e9di . Regular partitions of graphs. In J.C. Bremond, J.C. Fournier, M. Las Vergnas, and D. Sotteau, editors , Proc. Colloque Internationaux CNRS 260 -- Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes , pages 399 -- 401 , 1978 . 12 Endre Szemer\u00e9di. Regular partitions of graphs. In J.C. Bremond, J.C. Fournier, M. Las Vergnas, and D. Sotteau, editors, Proc. Colloque Internationaux CNRS 260 -- Probl\u00e8mes Combinatoires et Th\u00e9orie des Graphes, pages 399--401, 1978. 12"},{"key":"e_1_2_1_59_1","first-page":"126","volume-title":"Proc. 44th Annual IEEE Symposium on Foundations of Computer Science","author":"Ta-Shma Amnon","year":"2003","unstructured":"Amnon Ta-Shma , Shmuel Safra , and David Zuckerman . Extractors from Reed-Muller codes . In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science , page 126 , 2003 . 5 Amnon Ta-Shma, Shmuel Safra, and David Zuckerman. Extractors from Reed-Muller codes. In Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, page 126, 2003. 5"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.59"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.2140\/apde.2010.3.1"},{"key":"e_1_2_1_62_1","volume-title":"The inverse conjecture for the Gowers norm over finite fields in low characteristic. Ann. Comb., (to appear)","author":"Tao Terence","year":"2011","unstructured":"Terence Tao and Tamar Ziegler . The inverse conjecture for the Gowers norm over finite fields in low characteristic. Ann. Comb., (to appear) , 2011 . http:\/\/arxiv.org\/abs\/1101.1469. 9, 14 Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields in low characteristic. Ann. Comb., (to appear), 2011. http:\/\/arxiv.org\/abs\/1101.1469. 9, 14"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_71"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556663.2556678","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2556663.2556678","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:06Z","timestamp":1750234206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2556663.2556678"}},"subtitle":["on testing affine-invariant properties over finite fields"],"short-title":[],"issued":{"date-parts":[[2013,12,10]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,12,10]]}},"alternative-id":["10.1145\/2556663.2556678"],"URL":"https:\/\/doi.org\/10.1145\/2556663.2556678","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2013,12,10]]},"assertion":[{"value":"2013-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}