Abstract
We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field \({\mathbb{F}_q}\) and an extension field \({\mathbb{F}_{q^n}}\), a property is a set of functions mapping \({\mathbb{F}_{q^n}}\) to \({\mathbb{F}_q}\). The property is said to be affine-invariant if it is invariant under affine transformations of \({\mathbb{F}_{q^n}}\), linear if it is an \({\mathbb{F}_q}\) -vector space, and sparse if its size is polynomial in the domain size. Our work completes a line of work initiated by Grigorescu et al. (2009) and followed by Kaufman & Lovett (2011). The latter showed such a result for the case when q was prime. Extending to non-prime cases turns out to be non-trivial, and our proof involves some detours into additive combinatorics, as well as a new calculus for building property testers for affine-invariant linear properties.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Noga Alon, Eldar Fischer, Ilan Newman,& Asaf Shapira (2006). A combinatorial characterization of the testable graph properties: it’s all about regularity. In STOC, 251–260. ACM. ISBN 1-59593-134-1. URL http://doi.acm.org/10.1145/1132516.1132555.
Boaz Barak, Russell Impagliazzo & Avi Wigderson (2006). Extracting Randomness Using Few Independent Sources. SIAM Journal on Computing 36.
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka & Madhu Sudan (2011a). On Sums of Locally Testable Affine Invariant Properties. Electronic Colloquium on Computational Complexity (ECCC) 18, 79. URL http://eccc.hpi-web.de/report/2011/079.
Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka & Madhu Sudan (2011b). On Sums of Locally Testable Affine Invariant Properties. In Approximation, Randomization and yesCombinatorial Optimization. Algorithms and Techniques, volume 6845 of LNCS, 400–411.
Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman (2005a) Locally Testable Codes Require Redundant Testers. SICOMP.SIAM Journal on Computing 39(7): 3230–3247
Eli Ben-Sasson, Prahladh Harsha & Sofya Raskhodnikova (2005b). Some 3CNF Properties Are Hard to Test. SIAM Journal on Computing 35.
Eli Ben-Sasson & Madhu Sudan (2010). Limits on the rate of locally testable affine-invariant codes. Electronic Colloquium on Computational Complexity (ECCC) 17, 108. URL http://eccc.hpi-web.de/report/2010/108.
Eli Ben-Sasson & Madhu Sudan (2011). Limits on the Rate of Locally Testable Affine-Invariant Codes. In APPROX-RANDOM, volume 6845 of Lecture Notes in Computer Science, 412–423. Springer. ISBN 978-3-642-22934-3. URL http://dx.doi.org/10.1007/978-3-642-22935-0.
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie (2011) Testing Linear-Invariant Non-Linear Properties. Theory of Computing 7(1): 75–99
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami & Shachar Lovett (2013). Every locally characterized affine-invariant property is testable. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), 429–436. ACM Press.
Arnab Bhattacharyya, Elena Grigorescu & Asaf Shapira (2010). A unified framework for testing linear-invariant properties. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 478–487. IEEE Computer Society.
Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, Balázs Szegedy & Katalin Vesztergombi (2006). Graph limits and parameter testing. In STOC, 261–270. ACM. ISBN 1-59593-134-1. URL http://doi.acm.org/10.1145/1132516.1132556.
J. Bourgain, A.A Glibichuk & S.V. Konyagin (2006). Estimates for the Number of Sums and Products and for Exponential Sums in Fields of Prime Order. Journal of the London Mathematical Society 73(2): 380–398 URL http://jlms.oxfordjournals.org/content/73/2/380.abstract.
Bourgain J., Katz N., Tao T. (2004) A sum-product extimate in finite fields, and applications. GAFA 14: 27–57
James Arthur Cipra (2010). Waring’s number in finite fields. Ph.D. thesis, Kansas State University, Manhattan, Kansas, USA
Todd Cochrane & James Cipra (2011). Sum-product estimates applied to Waring’s problem over finite fields. INTEGERS 11.
Elena Grigorescu, Tali Kaufman & Madhu Sudan (2008). 2-Transitivity Is Insufficient for Local Testability. In IEEE Conference on Computational Complexity, 259–267. IEEE Computer Society. ISBN 978-0-7695-3169-4.
Elena Grigorescu, Tali Kaufman & Madhu Sudan (2009). Succint representation of codes with applications to testing. In Proceedings of RANDOM-APPROX 2009, volume 5687 of Lecture Notes in Computer Science, 534–547. Springer. URL http://dx.doi.org/10.1007/978-3-642-22935-0.
Tali Kaufman & Simon Litsyn (2005). Almost Orthogonal Linear Codes are Locally Testable. In FOCS, 317–326. IEEE Computer Society. ISBN 0-7695-2468-0.
Tali Kaufman & Shachar Lovett (2010). Testing of exponentially large codes, by a new extension to Weil bound for character sums. Electronic Colloquium on Computational Complexity (ECCC) 17, 65. URL http://eccc.hpi-web.de/report/2010/065.
Tali Kaufman & Shachar Lovett (2011). New extension of the Weil bound for character sums with applications to coding. In The 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011).
Tali Kaufman & Madhu Sudan (2007a). Algebraic Property Testing: The Role of Invariance. Electronic Colloquium on Computational Complexity (ECCC) 14(111). URL http://eccc.hpi-web.de/eccc-reports/2007/TR07-111/index.html.
Tali Kaufman & Madhu Sudan (2007b). Sparse Random Linear Codes are Locally Decodable and Testable. In FOCS, 590–600. IEEE Computer Society.
Tali Kaufman & Madhu Sudan (2008). Algebraic property testing: the role of invariance. In STOC, 403–412. ACM. ISBN 978-1-60558-047-0. URL http://doi.acm.org/10.1145/1374376.1374434.
Swastik Kopparty & Shubhangi Saraf (2010). Local list-decoding and testing of random linear codes from high error. In STOC, 417–426. ACM Press.
Schwartz J.T. (1980) Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4): 701–717
Asaf Shapira (2009). Greens conjecture and testing linear-invariant properties. In Proceedings of the 41st Annual ACM Symposium on the Theory of Computing (STOC), 159–166. ACM Press.
R. Zippel (1979). Probabilistic algorithms for sparse polynomials. In ISSAC ’79: Proc. Int’l. Symp. on Symbolic and Algebraic Computation, Lecture Notes in Computer Science, Vol. 72. Springer-Verlag.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ben-Sasson, E., Ron-Zewi, N. & Sudan, M. Sparse affine-invariant linear codes are locally testable. comput. complex. 26, 37–77 (2017). https://doi.org/10.1007/s00037-015-0115-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00037-015-0115-6