Linear-time list recovery of high-rate expander codes. (English) Zbl 1403.94105
Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-47671-0/pbk; 978-3-662-47672-7/ebook). Lecture Notes in Computer Science 9134, 701-712 (2015).
Summary: We show that expander codes, when properly instantiated, are high-rate list recoverable codes with linear-time list recovery algorithms. List recoverable codes have been useful recently in constructing efficiently list-decodable codes, as well as explicit constructions of matrices for compressive sensing and group testing. Previous list recoverable codes with linear-time decoding algorithms have all had rate at most \(1/2\); in contrast, our codes can have rate \(1 - {\varepsilon} \) for any \({\varepsilon} > 0\). We can plug our high-rate codes into a framework of N. Alon and M. Luby [IEEE Trans. Inf. Theory 42, No. 6, Pt. 1, 1732–1736 (1996; Zbl 0873.94024)] and O. Meir [“Locally correctable and testable codes approaching the singleton bound”. ECCC Report TR14-107 (2014)] to obtain linear-time list recoverable codes of arbitrary rates \(R\), which approach the optimal trade-off between the number of non-trivial lists provided and the rate of the code.{
}While list-recovery is interesting on its own, our primary motivation is applications to list-decoding. A slight strengthening of our result would imply linear-time and optimally list-decodable codes for all rates. Thus, our result is a step in the direction of solving this important problem.
The final version appeared in [Inf. Comput. 261, Part 2, 202–218 (2018; Zbl 1403.94106)].
For the entire collection see [Zbl 1316.68014].
The final version appeared in [Inf. Comput. 261, Part 2, 202–218 (2018; Zbl 1403.94106)].
For the entire collection see [Zbl 1316.68014].
References:
| [1] | Alon, N.; Luby, M., A linear time erasure-resilient code with nearly optimal recovery, IEEE Transactions on Information Theory, 42, 6, 1732-1736 (1996) · Zbl 0873.94024 · doi:10.1109/18.556669 |
| [2] | Barg, A.; Zemor, G., Error exponents of expander codes, IEEE Transactions on Information Theory, 48, 6, 1725-1729 (2002) · Zbl 1061.94078 · doi:10.1109/TIT.2002.1003853 |
| [3] | Barg, A.; Zemor, G., Concatenated codes: serial and parallel, IEEE Transactions on Information Theory, 51, 5, 1625-1634 (2005) · Zbl 1282.94098 · doi:10.1109/TIT.2005.846392 |
| [4] | Barg, A.; Zemor, G., Distance properties of expander codes, IEEE Transactions on Information Theory, 52, 1, 78-90 (2006) · Zbl 1282.94107 · doi:10.1109/TIT.2005.860415 |
| [5] | Dvir, Z., Lovett, S.: Subspace evasive sets. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 351-358. ACM (2012) · Zbl 1286.94109 |
| [6] | Gallager, R.G.: Low Density Parity-Check Codes. Technical report. MIT (1963) · Zbl 0107.11802 |
| [7] | Gilbert, AC; Ngo, HQ; Porat, E.; Rudra, A.; Strauss, MJ; Fomin, FV; Freivalds, R.; Kwiatkowska, M.; Peleg, D., \( \ell_\text{2 }/\ell_\text{2 } \)-foreach sparse recovery with low risk, Automata, Languages, and Programming, 461-472 (2013), Heidelberg: Springer, Heidelberg · Zbl 1336.68062 · doi:10.1007/978-3-642-39206-1_39 |
| [8] | Guruswami, V., List decoding from erasures: Bounds and code constructions, IEEE Transactions on Information Theory, 49, 11, 2826-2833 (2003) · Zbl 1301.94156 · doi:10.1109/TIT.2003.815776 |
| [9] | Guruswami, V., List decoding of error-correcting codes: winning thesis of the 2002 ACM doctoral dissertation competition (2004), Heidelberg: Springer, Heidelberg · Zbl 1075.94001 |
| [10] | Guruswami, V.: Linear-algebraic list decoding of folded reed-solomon codes. In: Proceedings of the 26th Annual Conference on Computational Complexity (CCC), pp. 77-85. IEEE (2011) |
| [11] | Guruswami, V., Indyk, P:. Expander-based constructions of efficiently decodable codes. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 658-667. IEEE (October 2001) |
| [12] | Guruswami, V., Indyk, P.: Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. In: Proceedings of the 34th Annual ACM Aymposium on Theory of computing (STOC), pp. 812-821. ACM (2002) · Zbl 1192.94132 |
| [13] | Guruswami, V., Indyk, P.: Linear time encodable and list decodable codes. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 126-135. ACM, New York (2003) · Zbl 1192.94097 |
| [14] | Guruswami, V.; Indyk, P.; Díaz, J.; Karhumäki, J.; Lepistö, A.; Sannella, D., Linear-time list decoding in error-free settings, Automata, Languages and Programming, 695-707 (2004), Heidelberg: Springer, Heidelberg · Zbl 1099.94522 · doi:10.1007/978-3-540-27836-8_59 |
| [15] | Guruswami, V., Kopparty, S.: Explicit subspace designs. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computing (FOCS), pp. 608-617. IEEE (2013) · Zbl 1389.51003 |
| [16] | Guruswami, V.; Rudra, A., Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy, IEEE Transactions on Information Theory, 54, 1, 135-150 (2008) · Zbl 1205.94125 · doi:10.1109/TIT.2007.911222 |
| [17] | Guruswami, V., Sudan, M.: Improved decoding of Reed-Solomon and algebraic-geometry codes. IEEE Transactions on Information Theory 45(6) (1999) · Zbl 0958.94036 |
| [18] | Guruswami, V., Xing, C.: Folded codes from function field towers and improved optimal rate list decoding. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pp. 339-350. ACM (2012) · Zbl 1286.94111 |
| [19] | Guruswami, V., Xing, C.: List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pp. 843-852. ACM (2013) · Zbl 1293.94110 |
| [20] | Hemenway, B., Ostrovsky, R., Wootters, M.: Local correctability of expander codes. Information and Computation (2014) · Zbl 1328.94102 |
| [21] | Hemenway, B., Wootters, M.: Linear-time list recovery of high-rate expander codes. ArXiv preprint 1503.01955 (2015) · Zbl 1403.94105 |
| [22] | Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bulletin of the American Mathematical Society, 43, 4, 439-561 (2006) · Zbl 1147.68608 · doi:10.1090/S0273-0979-06-01126-8 |
| [23] | Indyk, P., Ngo, H.Q., Rudra, A.: Efficiently decodable non-adaptive group testing. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1126-1142. Society for Industrial and Applied Mathematics (2010) · Zbl 1288.68123 |
| [24] | Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 3, 261-277 (1988) · Zbl 0661.05035 · doi:10.1007/BF02126799 |
| [25] | Margulis, GA, Explicit Group-Theoretical Constructions of Combinatorial Schemes and Their Application to the Design of Expanders and Concentrators, Probl. Peredachi Inf., 24, 1, 51-60 (1988) · Zbl 0708.05030 |
| [26] | Meir, O.: Locally correctable and testable codes approaching the singleton bound, ECCC Report TR14-107 (2014) |
| [27] | Morgenstern, M., Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power q, Journal of Combinatorial Theory, Series B, 62, 1, 44-62 (1994) · Zbl 0814.68098 · doi:10.1006/jctb.1994.1054 |
| [28] | Ngo, H.Q., Porat, E., Rudra, A.: Efficiently decodable compressed sensing by list-recoverable codes and recursion. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), vol. 14, pp. 230-241 (2012) · Zbl 1245.94043 |
| [29] | Sipser, M., Spielman, D.A.: Expander codes. IEEE Transactions in Information Theory 42(6) (1996) · Zbl 0943.94543 |
| [30] | Tanner, R., A recursive approach to low complexity codes, IEEE Transactions on Information Theory, 27, 5, 533-547 (1981) · Zbl 0474.94029 · doi:10.1109/TIT.1981.1056404 |
| [31] | Zemor, G., On expander codes, IEEE Transactions on Information Theory, 47, 2, 835-837 (2001) · Zbl 1021.94025 · doi:10.1109/18.910593 |
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.
