Abstract
Motivated by questions in property testing, we search for linear error-correcting codes that have the “single local orbit” property: they are specified by a single local constraint and its translations under the symmetry group of the code. We show that the dual of every “sparse” binary code whose coordinates are indexed by elements of \({\mathbb{F}}_{2^n}\) for prime n, and whose symmetry group includes the group of non-singular affine transformations of \({\mathbb{F}}_{2^n}\), has the single local orbit property. (A code is sparse if it contains polynomially many codewords in its block length.) In particular this class includes the dual-BCH codes for whose duals (BCH codes) simple bases were not known. Our result gives the first short (O(n)-bit, as opposed to \(\exp(n)\)-bit) description of a low-weight basis for BCH codes. If 2n − 1 is a Mersenne prime, then we get that every sparse cyclic code also has the single local orbit.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing Reed-Muller codes. IEEE Transactions on Information Theory 51(11), 4032–4039 (2005)
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. Journal of Computer and System Sciences 47(3), 549–595 (1993)
Bourgain, J.: Mordell’s exponential sum estimate revisited. J. Amer. Math. Soc. 18(2), 477–499 (2005) (electronic)
Bourgain, J.: Some arithmetical applications of the sum-product theorems in finite fields. In: Geometric aspects of functional analysis. Lecture Notes in Math., vol. 1910, pp. 99–116. Springer, Berlin (2007)
Bourgain, J., Katz, N., Tao, T.: A sum-product estimate in finite fields, and applications. Geom. Funct. Anal. 14(1), 27–57 (2004)
Bourgain, J., Chang, M.-C.: A Gauss sum estimate in arbitrary finite fields. C. R. Math. Acad. Sci. Paris 342(9), 643–646 (2006)
Bourgain, J., Konyagin, S.V.: Estimates for the number of sums and products and for exponential sums over subgroups in fields of prime order. C. R. Math. Acad. Sci. Paris 337(2), 75–80 (2003)
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM 45(4), 653–750 (1998)
Goldreich, O., Sudan, M.: Locally testable codes and PCPs of almost-linear length. J. ACM 53(4), 558–655 (2002); Preliminary version in FOCS 2002
Jutla, C.S., Patthak, A.C., Rudra, A., Zuckerman, D.: Testing low-degree polynomials over prime fields. In: FOCS 2004, pp. 423–432. IEEE Computer Society Press, Los Alamitos (2004)
Kaufman, T., Litsyn, S.: Almost orthogonal linear codes are locally testable. In: FOCS, pp. 317–326. IEEE Computer Society Press, Los Alamitos (2005)
Kaufman, T., Litsyn, S.: Long extended BCH codes are spanned by minimum weight words. In: Fossorier, M.P.C., Imai, H., Lin, S., Poli, A. (eds.) AAECC 2006. LNCS, vol. 3857, pp. 285–294. Springer, Heidelberg (2006)
Kaufman, T., Ron, D.: Testing polynomials over general fields. SIAM J. Comput. 36(3), 779–802 (2006)
Kaufman, T., Sudan, M.: Sparse random linear codes are locally decodable and testable. In: FOCS, pp. 590–600. IEEE Computer Society Press, Los Alamitos (2007)
Kaufman, T., Sudan, M.: Algebraic property testing: the role of invariance. In: Ladner, R.E., Dwork, C. (eds.) STOC, pp. 403–412. ACM Press, New York (2008)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier/North-Holland, Amsterdam (1981)
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)
van Lint, J.H.: Introduction to Coding Theory, 3rd edn. Graduate Texts in Mathematics, vol. 86. Springer, Berlin (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grigorescu, E., Kaufman, T., Sudan, M. (2009). Succinct Representation of Codes with Applications to Testing. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. APPROX RANDOM 2009 2009. Lecture Notes in Computer Science, vol 5687. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03685-9_40
Download citation
DOI: https://doi.org/10.1007/978-3-642-03685-9_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03684-2
Online ISBN: 978-3-642-03685-9
eBook Packages: Computer ScienceComputer Science (R0)