{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:49:51Z","timestamp":1750308591336,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,4,27]],"date-time":"2017-04-27T00:00:00Z","timestamp":1493251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DSTO1358 Ramanujan Fellowship"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1523816 and CCF-1217416"],"award-info":[{"award-number":["CCF-1523816 and CCF-1217416"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"<jats:p>\n            Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well suited to admit local correctors and testers. In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code\n            <jats:italic>C<\/jats:italic>\n            \u2282 \u03a3\n            <jats:sup>\n              K\n              <jats:sup>\n                <jats:italic>n<\/jats:italic>\n              <\/jats:sup>\n            <\/jats:sup>\n            is an\n            <jats:italic>r<\/jats:italic>\n            -query affine invariant locally correctable code (LCC), where K is a finite field and \u03a3 is a finite alphabet, then the number of codewords in\n            <jats:italic>C<\/jats:italic>\n            is at most exp(\n            <jats:italic>O<\/jats:italic>\n            <jats:sub>K,r,|\u03a3|<\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>r<\/jats:italic>\n              \u22121))\n            <\/jats:sup>\n            . Also, we show that if\n            <jats:italic>C<\/jats:italic>\n            \u2282 \u03a3\n            <jats:sup>K<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            is an\n            <jats:italic>r<\/jats:italic>\n            -query affine invariant locally testable code (LTC), then the number of codewords in\n            <jats:italic>C<\/jats:italic>\n            is at most exp(\n            <jats:italic>O<\/jats:italic>\n            <jats:sub>K,r,|\u03a3|<\/jats:sub>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>r<\/jats:italic>\n              \u22122))\n            <\/jats:sup>\n            . The dependence on\n            <jats:italic>n<\/jats:italic>\n            in these bounds is tight for constant-query LCCs\/LTCs, since Guo, Kopparty, and Sudan (ITCS\u201913) constructed affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM\u201911) assumed linearity to derive similar results. Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC\/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems, which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, up to a small error in the Gowers norm.\n          <\/jats:p>","DOI":"10.1145\/3016802","type":"journal-article","created":{"date-parts":[[2017,4,28]],"date-time":"2017-04-28T12:38:23Z","timestamp":1493383103000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs"],"prefix":"10.1145","volume":"9","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"Indian Institute of Science, Bangalore, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sivakanth","family":"Gopi","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,4,27]]},"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":"crossref","unstructured":"Boaz Barak Zeev Dvir Amir Yehudayoff and Avi Wigderson. 2011. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. ACM 519--528.  Boaz Barak Zeev Dvir Amir Yehudayoff and Avi Wigderson. 2011. Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes. ACM 519--528.","DOI":"10.1145\/1993636.1993705"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74208-1_23"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.38"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Eli Ben-Sasson and Madhu Sudan. 2004. Robust locally testable codes and products of codes. 286--297.  Eli Ben-Sasson and Madhu Sudan. 2004. Robust locally testable codes and products of codes. 286--297.","DOI":"10.1007\/978-3-540-27821-4_26"},{"key":"e_1_2_1_7_1","volume-title":"Short PCPs with polylog query complexity. 38, 2","author":"Ben-Sasson Eli","year":"2008","unstructured":"Eli Ben-Sasson and Madhu Sudan . 2008. Short PCPs with polylog query complexity. 38, 2 ( 2008 ), 551--607. Eli Ben-Sasson and Madhu Sudan. 2008. Short PCPs with polylog query complexity. 38, 2 (2008), 551--607."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22935-0_35"},{"key":"e_1_2_1_9_1","volume-title":"Using higher-order Fourier analysis over general fields. Preprint arXiv:1505.00619","author":"Bhattacharyya Arnab","year":"2015","unstructured":"Arnab Bhattacharyya and Abhishek Bhowmick . 2015. Using higher-order Fourier analysis over general fields. Preprint arXiv:1505.00619 ( 2015 ). Arnab Bhattacharyya and Abhishek Bhowmick. 2015. Using higher-order Fourier analysis over general fields. Preprint arXiv:1505.00619 (2015)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.28"},{"key":"e_1_2_1_11_1","volume-title":"Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. Preprint arXiv:1506.02047","author":"Bhowmick Abhishek","year":"2015","unstructured":"Abhishek Bhowmick and Shachar Lovett . 2015a. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. Preprint arXiv:1506.02047 ( 2015 ). Abhishek Bhowmick and Shachar Lovett. 2015a. Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory. Preprint arXiv:1506.02047 (2015)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746543"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/200836.200880"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236459"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591818"},{"key":"e_1_2_1_18_1","volume-title":"Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. 36, 5","author":"Dvir Zeev","year":"2007","unstructured":"Zeev Dvir and Amir Shpilka . 2007. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. 36, 5 ( 2007 ), 1404--1434. Zeev Dvir and Amir Shpilka. 2007. Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. 36, 5 (2007), 1404--1434."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 17th IEEE Annual Conference on Computational Complexity. IEEE, 175--183","author":"Goldreich Oded","year":"2012","unstructured":"Oded Goldreich , Howard Karloff , Leonard J. Schulman , and Luca Trevisan . 2012 . Lower bounds for linear locally decodable codes and private information retrieval . In Proceedings of the 17th IEEE Annual Conference on Computational Complexity. IEEE, 175--183 . Oded Goldreich, Howard Karloff, Leonard J. Schulman, and Luca Trevisan. 2012. Lower bounds for linear locally decodable codes and private information retrieval. In Proceedings of the 17th IEEE Annual Conference on Computational Complexity. IEEE, 175--183."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1162349.1162351"},{"key":"e_1_2_1_21_1","volume-title":"A new proof of Szemer\u00e9di\u2019s theorem. 11, 3","author":"Gowers William T.","year":"2001","unstructured":"William T. Gowers . 2001. A new proof of Szemer\u00e9di\u2019s theorem. 11, 3 ( 2001 ), 465--588. William T. Gowers. 2001. A new proof of Szemer\u00e9di\u2019s theorem. 11, 3 (2001), 465--588."},{"key":"e_1_2_1_22_1","volume-title":"Montreal lecture notes on quadratic Fourier analysis. Preprint arXiv:math\/0604089","author":"Green Ben","year":"2006","unstructured":"Ben Green . 2006. Montreal lecture notes on quadratic Fourier analysis. Preprint arXiv:math\/0604089 ( 2006 ). Ben Green. 2006. Montreal lecture notes on quadratic Fourier analysis. Preprint arXiv:math\/0604089 (2006)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422494"},{"volume-title":"Some Closure Features of Locally Testable Affine-invariant Properties. Master\u2019s thesis","author":"Guo Alan Xinyu","key":"e_1_2_1_24_1","unstructured":"Alan Xinyu Guo . 2013. Some Closure Features of Locally Testable Affine-invariant Properties. Master\u2019s thesis . Massachusetts Institute of Technology . Alan Xinyu Guo. 2013. Some Closure Features of Locally Testable Affine-invariant Properties. Master\u2019s thesis. Massachusetts Institute of Technology."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.87"},{"key":"e_1_2_1_26_1","first-page":"5","article-title":"Some results on cyclic codes which are invariant under the affine group and their applications","volume":"11","author":"Kasami T.","year":"1967","unstructured":"T. Kasami , S. Lin , and W. W. Peterson . 1967 . Some results on cyclic codes which are invariant under the affine group and their applications . Inform. and Comput. 11 , 5 -- 6 (1967), 475--496. T. Kasami, S. Lin, and W. W. Peterson. 1967. Some results on cyclic codes which are invariant under the affine group and their applications. Inform. and Comput. 11, 5--6 (1967), 475--496.","journal-title":"Inform. and Comput."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Tali Kaufman and Madhu Sudan. 2008. Algebraic property testing: The role of invariance. ACM 403--412.  Tali Kaufman and Madhu Sudan. 2008. Algebraic property testing: The role of invariance. ACM 403--412.","DOI":"10.1145\/1374376.1374434"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Iordanis Kerenidis and Ronald de Wolf. 2003. Exponential lower bound for 2-query locally decodable codes via a quantum argument. ACM 106--115.  Iordanis Kerenidis and Ronald de Wolf. 2003. Exponential lower bound for 2-query locally decodable codes via a quantum argument. ACM 106--115.","DOI":"10.1145\/780542.780560"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-52282-4_44"},{"key":"e_1_2_1_31_1","volume-title":"Combinatorial construction of locally testable codes. 39, 2","author":"Meir Or","year":"2009","unstructured":"Or Meir . 2009. Combinatorial construction of locally testable codes. 39, 2 ( 2009 ), 491--544. Or Meir. 2009. Combinatorial construction of locally testable codes. 39, 2 (2009), 491--544."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766253"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/142"},{"key":"e_1_2_1_34_1","volume-title":"The inverse conjecture for the Gowers norm over finite fields in low characteristic. 16, 1","author":"Tao Terence","year":"2012","unstructured":"Terence Tao and Tamar Ziegler . 2012. The inverse conjecture for the Gowers norm over finite fields in low characteristic. 16, 1 ( 2012 ), 121--188. Terence Tao and Tamar Ziegler. 2012. The inverse conjecture for the Gowers norm over finite fields in low characteristic. 16, 1 (2012), 121--188."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/12086827X"},{"key":"e_1_2_1_36_1","first-page":"20","article-title":"Explicit strong LTCs with inverse poly-log rate and constant soundness","volume":"22","author":"Viderman Michael","year":"2015","unstructured":"Michael Viderman . 2015 . Explicit strong LTCs with inverse poly-log rate and constant soundness . Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 20 . Michael Viderman. 2015. Explicit strong LTCs with inverse poly-log rate and constant soundness. Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 20.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_37_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC)","volume":"14","author":"Woodruff David","year":"2007","unstructured":"David Woodruff . 2007 . New lower bounds for general locally decodable codes . In Electronic Colloquium on Computational Complexity (ECCC) , Vol. 14 . David Woodruff. 2007. New lower bounds for general locally decodable codes. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 14."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-012-1254-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20712-9_22"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3016802","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3016802","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3016802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:22Z","timestamp":1750273522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3016802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,27]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3016802"],"URL":"https:\/\/doi.org\/10.1145\/3016802","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2017,4,27]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}