Abstract
Coding theoretic and complexity theoretic considerations naturally lead to the question of generating symmetric, sparse, redundant linear systems. This paper provides new way of constructions with better parameters and new lower bounds.
Low Density Parity Check (LDPC) codes are linear codes defined by short constraints (a property essential for local testing of a code). Some of the best (theoretically and practically) used codes are LDPC. Symmetric codes are those in which all coordinates “look the same”, namely there is some transitive group acting on the coordinates which preserves the code. Some of the most commonly used locally testable codes (especially in PCPs and other proof systems), including all “low-degree” codes, are symmetric. Requiring that a symmetric binary code of length n has large (linear or near-linear) distance seems to suggest a “conflict” between 1/rate and density (constraint length). In known constructions, if one is constant then the other is almost worst possible - n/poly(logn).
Our main positive result simultaneously achieves symmetric low density, constant rate codes generated by a single constraint. We present an explicit construction of a symmetric and transitive binary code of length n, near-linear distance n/(loglogn)2, of constant rate and with constraints of length (logn)4. The construction is in the spirit of Tanner codes, namely the codewords are indexed by the edges of a sparse regular expander graph. The main novelty is in our construction of a transitive (non Abelian!) group acting on these edges which preserves the code. Our construction is one instantiation of a framework we call Cayley Codes developed here, that may be viewed as extending zig-zag product to symmetric codes.
Our main negative result is that the parameters obtained above cannot be significantly improved, as long as the acting group is solvable (like the one we use). More specifically, we show that in constant rate and linear distance codes (aka ”good” codes) invariant under solvable groups, the density (length of generating constraints) cannot go down to a constant, and is bounded below by log(Ω(ℓ)) n if the group has a derived series of length ℓ. This negative result precludes natural local tests with constantly many queries for such solvable ”good” codes.
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 Low Degree Polynomials Over GF(2). In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 188–199. Springer, Heidelberg (2003); Also IEEE Transactions on Information Theory 51(11), 4032–4039 (2005)
Alon, N., Lubotzky, A., Wigderson, A.: Semi Direct product in groups and zig-zag product in graphs: connections and applictions. In: Proceedings of the 42nd Annual Symposium on the Foundations of Computer Science (FOCS), pp. 630–637 (2001)
Arora, S., Sudan, M.: Improved low degree testing and its applications. Combinatorica 23(3), 365–426 (2003)
Babai, L., Fortnow, L., Lund, C.: Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity 1(1), 3–40 (1991)
Babai, L., Shpilka, A., Stefankovic, D.: Locally testable cyclic codes. IEEE Transactions on Information Theory 51(8), 2849–2858 (2005)
Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF Properties are Hard to Test. SIAM Journal on Computing 35(1), 1–21 (2005)
Ben-Sasson, E., Sudan, M.: Simple PCPs with poly-log rate and query complexity. In: STOC 2005, 266–275 (2005)
Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets. In: 35th Annual ACM Symposium, STOC 2003, pp. 612–621 (2003)
Berman, S.D.: Semisimple Cyclic and Abelian Codes. Cybernetics 3, 21–30 (1967)
Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. J. Comp. Sys. Sci. 47(3) (December 1993)
Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness Conductors and Constant-Degree Expansion Beyond the Degree/2 Barrier. In: Proceedings of the 34th STOC, pp. 659–668 (2002)
Carlitz, L., Uchiyama, S.: Bounds for exponential sums. Duke Math. J. 24, 37–41 (1957)
Dinur, I.: The PCP theorem by gap amplification. J. ACM 54(3), 12 (2007)
Gallager, R.G.: Low density parity check codes. MIT Press, Cambridge (1963)
Grigorescu, E., Kaufman, T., Sudan, M.: Succinct Representation of Codes with Applications to Testing (manuscript)
Goldreich, O., Sudan, M.: Locally testable codes and PCPs of almost-linear length. J. ACM 53(4), 558–655 (2006)
Holton, D.A., Sheehan, J.: The Petersen Graph. Cambridge University Press, Cambridge (1993)
Kaufman, T., Sudan, M.: Algebraic Property Testing: The Role of Invariance. In: Proceedings of the 40th ACM Symposium on Theory of Computing, STOC (2008)
Kaufman, T., Litsyn, S.: Almost Orthogonal Linear Codes are Locally Testable. In: FOCS 2005, pp. 317–326 (2005)
Lackenby, M.: Large groups, property (τ) and the homology growth of subgroups. Math. Proc. Cambridge Philos. Soc. 146(3), 625–648 (2009)
Lackenby, M.: Covering spaces of 3-orbifolds. Duke Math. J. 136(1), 181–203 (2007)
Luby, M.G., Mitzenmacher, M., Amin Shokrollahi, M., Spielman, D.A.: Improved Low-Density Parity-Check Codes Using Irregular Graphs. IEEE Transactions on Information Theory 47(2), 585–598 (2001)
Lubotzky, A., Weiss, B.: Groups and expanders. In: Friedman, e.J. (ed.) Expanding Graphs. DIMACS Ser. Discrete Math. Theoret. Compt. Sci., vol. 10, pp. 95–109. Amer. Math. Soc., Providence (1993)
MacWilliams, F.J., Sloan, N.J.A.: The Theory of Error Correcting Codes. North Holland, Amsterdam (1977)
McElice, R.J.: On the Symmetry of Good Nonlinear Codes. IEEE Trans. Inform. Theory IT-16, 609–611 (1970)
Meir, O.: Combinatorial Construction of Locally Testable Codes. In: Proceedings of STOC 2008, pp. 285–294 (2008)
Meshulam, R., Wigderson, A.: Expanders in Group Algebras. Combinatorica 24(4), 659–680 (2004)
Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing 25(2), 252–271 (1996)
Rozenman, E., Shalev, A., Wigderson, A.: A new family of Cayley expanders (?) In: 36th Annual ACM Symposium, STOC 2004, pp. 445–454 (2004)
Richardson, T., Urbanke, R.: The Capacity of Low-Density Parity Check Codes under Message-Passing Decoding. IEEE Transactions on Information Theory 47(2), 599–618 (2001)
Reingold, O., Vadhan, S., Wigderson, A.: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders. Annals of Mathematics 155(1), 157–187 (2002)
Sipser, M., Spielman, D.A.: Expander codes. IEEE Transactions on Information Theory 42(6), 1710–1722 (1996)
Sudan, M.: Lecture notes, http://people.csail.mit.edu/madhu/FT01/scribe/bch.ps
Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR Lemma. Journal of Computer and System Sciences 62(2), 236–266 (2001)
Tanner, R.M.: A recursive approach to low complexity codes. IEEE Transactions on Information Theory 27(5), 533–547 (1981)
Weil, A.: Sur les courbes algebriques et les varietes qui s’en deduisent. Actualities Sci. et Ind. no. 1041. Hermann, Paris (1948)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Kaufman, T., Wigderson, A. (2010). Symmetric LDPC Codes and Local Testing. In: Goldreich, O. (eds) Property Testing. Lecture Notes in Computer Science, vol 6390. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16367-8_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-16367-8_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16366-1
Online ISBN: 978-3-642-16367-8
eBook Packages: Computer ScienceComputer Science (R0)