×

Local correctability of expander codes. (English) Zbl 1329.94090

Summary: In this work, we present the first local-decoding algorithm for expander codes. This yields a new family of constant-rate codes that can recover from a constant fraction of errors in the codeword symbols, and where any symbol of the codeword can be recovered with high probability by reading \(N^\varepsilon\) symbols from the corrupted codeword, where \(N\) is the block-length of the code.{ } Expander codes, introduced by M. Sipser and D. A. Spielman [IEEE Trans. Inf. Theory 42, No. 6, Part 1, 1710–1722 (1996; Zbl 0943.94543)], are formed from an expander graph \(G = (V, E)\) of degree \(d\), and an inner code of block-length \(d\) over an alphabet \(\Sigma\). Each edge of the expander graph is associated with a symbol in \(\Sigma\). A string in \(\Sigma^E\) will be a codeword if for each vertex in \(V\), the symbols on the adjacent edges form a codeword in the inner code.{ } We show that if the inner code has a smooth reconstruction algorithm in the noiseless setting, then the corresponding expander code has an efficient local-correction algorithm in the noisy setting. Instantiating our construction with inner codes based on finite geometries, we obtain novel locally decodable codes with rate approaching one. This provides an alternative to the multiplicity codes of Kopparty, Saraf and Yekhanin [S. Kopparty et al., STOC 2011, New York, NY: ACM, 167–176 (2011; Zbl 1288.94112)] and the lifted codes of Guo, Kopparty and Sudan [A. Guo et al., Innovations in Theoretical Computer Science, ITCS 2013, New York, NY: ACM, 529–540 (2013), doi:10.1145/2422436.2422494].

MSC:

94B05 Linear codes (general theory)
94B35 Decoding
Full Text: DOI

References:

[1] Alon, N.; Feige, U.; Wigderson, A.; Zuckerman, D., Derandomized graph products, Comput. Complex., 5, 1, 60-75 (1995) · Zbl 0816.60070
[2] Assmus, E. F.; Key, J. D., Designs and Their Codes, vol. 103 (1994), Cambridge University Press · Zbl 0762.05001
[3] Assmus, E. F.; Key, J. D., Polynomial codes and finite geometries, (Handbook of Coding Theory, vol. 2 (1998)), 1269-1343 · Zbl 0980.94038
[4] Babai, László; Fortnow, Lance; Levin, Leonid A.; Szegedy, Mario, Checking computations in polylogarithmic time, (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991), ACM: ACM New York, NY, USA), 21-32
[5] Barg, A.; Zemor, G., Error exponents of expander codes, IEEE Trans. Inf. Theory, 48, 6, 1725-1729 (June 2002) · Zbl 1061.94078
[6] Barg, A.; Zemor, G., Concatenated codes: serial and parallel, IEEE Trans. Inf. Theory, 51, 5, 1625-1634 (May 2005) · Zbl 1282.94098
[7] Barg, A.; Zemor, G., Distance properties of expander codes, IEEE Trans. Inf. Theory, 52, 1, 78-90 (January 2006) · Zbl 1282.94107
[8] Beimel, Amos; Ishai, Yuval; Kushilevitz, Eyal; Orlov, Ilan, Share conversion and private information retrieval, (Proceedings of the 27th Annual IEEE Conference on Computational Complexity (2012), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA, USA), 258-268
[9] Ben-Aroya, A.; Efremenko, K.; Ta-Shma, A., Local list decoding with a constant number of queries, (Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (October 2010), IEEE), 715-722
[10] Blum, M.; Luby, M.; Rubinfeld, R., Self-testing/correcting with applications to numerical problems, (Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (1990), ACM: ACM New York, NY, USA), 73-83
[11] Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt, Self-testing/correcting with applications to numerical problems, J. Comput. Syst. Sci., 47, 3, 549-595 (December 1993) · Zbl 0795.68131
[12] Chee, Yeow M.; Feng, Tao; Ling, San; Wang, Huaxiong; Zhang, Liang F., Query-efficient locally decodable codes of subexponential length, Comput. Complex., 1-31 (August 2011)
[13] Dvir, Zeev; Gopalan, Parikshit; Yekhanin, Sergey, Matching vector codes, SIAM J. Comput., 40, 4, 1154-1178 (January 2011) · Zbl 1228.68026
[14] Efremenko, Klim, 3-Query locally decodable codes of subexponential length, (Proceedings of the 41st Annual ACM Symposium on Theory of Computing (2009), ACM), 39-44 · Zbl 1304.94124
[15] Efremenko, Klim, From irreducible representations to locally decodable codes, (Proceedings of the 44th Symposium on Theory of Computing (2012), ACM: ACM New York, NY, USA), 327-338 · Zbl 1286.94101
[16] Gallager, R. G., Low density parity-check codes (1963), MIT, Technical report · Zbl 0107.11802
[17] Gemmell, Peter; Lipton, Richard J.; Rubinfeld, Ronitt; Sudan, Madhu; Wigderson, Avi, Self-testing/correcting for polynomials and for approximate functions, (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (1991), ACM: ACM New York, NY, USA), 33-42
[18] Gemmell, Peter; Sudan, Madhu, Highly resilient correctors for polynomials, Inf. Process. Lett., 43, 4, 169-174 (September 1992) · Zbl 0767.68075
[19] Gillman, D., A Chernoff bound for random walks on expander graphs, SIAM J. Comput., 27, 4, 1203-1220 (1998) · Zbl 0911.60016
[20] Guo, A.; Kopparty, S.; Sudan, M., New affine-invariant codes from lifting, (Proceedings of the 4th Conference on Innovations in Theoretical Computer Science (2013), ACM: ACM New York, NY, USA), 529-540 · Zbl 1364.94606
[21] Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Am. Math. Soc., 43, 4, 439-562 (2006) · Zbl 1147.68608
[22] Impagliazzo, R.; Kabanets, V., Constructive proofs of concentration bounds, (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (2010)), 617-631 · Zbl 1305.68331
[23] Itoh, Toshiya; Suzuki, Yasuhiro, New constructions for query-efficient locally decodable codes of subexponential length, IEICE Trans. Inf. Syst. E, 93, D(2), 263-270 (October 2010)
[24] Katz, Jonathan; Trevisan, Luca, On the efficiency of local decoding procedures for error-correcting codes, (Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (2000)), 80-86 · Zbl 1296.94171
[25] Kopparty, S.; Saraf, S.; Yekhanin, S., High-rate codes with sublinear-time decoding, (Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (2011), ACM), 167-176 · Zbl 1288.94112
[26] Lipton, Richard J., Efficient checking of computations, (Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings of the 7th Annual Symposium on Theoretical Aspects of Computer Science, New York, NY, USA (1990), Springer-Verlag: Springer-Verlag New York), 207-215 · Zbl 0729.68030
[27] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 3, 261-277 (1988) · Zbl 0661.05035
[28] Margulis, G. A., Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, Probl. Inf. Transm., 9, 1, 39-46 (1988) · Zbl 0708.05030
[29] Morgenstern, M., Existence and explicit constructions of \(q + 1\) regular Ramanujan graphs for every prime power \(q\), J. Comb. Theory, Ser. B, 62, 1, 44-62 (1994) · Zbl 0814.68098
[30] Polishchuk, Alexander; Spielman, Daniel A., Nearly-linear size holographic proofs, (Proceedings of the 26th Annual ACM Symposium on Theory of Computing. Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC ’94 (1994), ACM: ACM New York, NY, USA), 194-203 · Zbl 1345.68180
[31] Reed, I., A class of multiple-error-correcting codes and the decoding scheme, Trans. IRE Prof. Group Inf. Theory, 4, 4, 38-49 (September 1954)
[32] Sipser, M.; Spielman, D. A., Expander codes, IEEE Trans. Inf. Theory, 42, 6, 1710-1722 (1996) · Zbl 0943.94543
[33] Spielman, D. A., Highly fault-tolerant parallel computation, (Proceedings of 37th Annual Symposium on Foundations of Computer Science (October 1996), IEEE), 154-163
[34] Spielman, D. A., Linear-time encodable and decodable error-correcting codes, IEEE Trans. Inf. Theory, 42, 6, 1723-1731 (November 1996) · Zbl 0943.94544
[35] Tanner, R., A recursive approach to low complexity codes, IEEE Trans. Inf. Theory, 27, 5, 533-547 (1981) · Zbl 0474.94029
[36] Yekhanin, Sergey, Towards 3-query locally decodable codes of subexponential length, (Proceedings of the 39th Annual ACM Symposium on Theory of Computing (2007), ACM), 266-274 · Zbl 1232.94020
[37] Yekhanin, Sergey, Towards 3-query locally decodable codes of subexponential length, J. ACM, 55, 1 (2008) · Zbl 1311.94125
[38] Yekhanin, Sergey, Locally decodable codes, Found. Trends Theor. Comput. Sci. (2010) · Zbl 1278.94002
[39] Zemor, G., On expander codes, IEEE Trans. Inf. Theory, 47, 2, 835-837 (2001) · Zbl 1021.94025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.