Folded codes from function field towers and improved optimal rate list decoding
We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/ε), matching the existential bound for random c...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Online Access: | https://hdl.handle.net/10356/99006 http://hdl.handle.net/10220/12643 |
| _version_ | 1826121141216870400 |
|---|---|
| author | Guruswami, Venkatesan Xing, Chaoping |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Guruswami, Venkatesan Xing, Chaoping |
| author_sort | Guruswami, Venkatesan |
| collection | NTU |
| description | We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on ε - it can be made exp(Õ(1/ ε 2)) which is not much worse than the non-constructive exp(1/ε) bound of random codes. The code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time O ε(N c) for an absolute constant c, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of function fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list-size and alphabet size polylogarithmic in the block length N. In comparison, algebraic codes achieving the optimal trade-off between list decodability and rate based on folded Reed-Solomon codes have a decoding complexity of N Ω(1/ε), an alphabet size of N Ω(1/ε2), and a list size of O(1/ε 2) (even after combination with subspace-evasive sets). Thus we get an improvement over the previous best bounds in all three aspects simultaneously, and are quite close to the existential random coding bounds. Along the way, we shed light on how to use automorphisms of certain function fields to enable list decoding of the folded version of the associated algebraic-geometric codes. |
| first_indexed | 2024-10-01T05:27:52Z |
| format | Conference Paper |
| id | ntu-10356/99006 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:27:52Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/990062020-03-07T12:31:20Z Folded codes from function field towers and improved optimal rate list decoding Guruswami, Venkatesan Xing, Chaoping School of Physical and Mathematical Sciences Symposium on Theory of Computing (44th : 2012) We give a new construction of algebraic codes which are efficiently list decodable from a fraction 1-R-ε of adversarial errors where R is the rate of the code, for any desired positive constant ε. The worst-case list size output by the algorithm is O(1/ε), matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on ε - it can be made exp(Õ(1/ ε 2)) which is not much worse than the non-constructive exp(1/ε) bound of random codes. The code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time O ε(N c) for an absolute constant c, where N is the code's block length. Our construction is based on a careful combination of a linear-algebraic approach to list decoding folded codes from towers of function fields, with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth (GS for short) tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list-size and alphabet size polylogarithmic in the block length N. In comparison, algebraic codes achieving the optimal trade-off between list decodability and rate based on folded Reed-Solomon codes have a decoding complexity of N Ω(1/ε), an alphabet size of N Ω(1/ε2), and a list size of O(1/ε 2) (even after combination with subspace-evasive sets). Thus we get an improvement over the previous best bounds in all three aspects simultaneously, and are quite close to the existential random coding bounds. Along the way, we shed light on how to use automorphisms of certain function fields to enable list decoding of the folded version of the associated algebraic-geometric codes. 2013-07-31T07:11:29Z 2019-12-06T20:02:14Z 2013-07-31T07:11:29Z 2019-12-06T20:02:14Z 2012 2012 Conference Paper Guruswami, V., & Xing, C. (2012). Folded codes from function field towers and improved optimal rate list decoding. Proceedings of the 44th symposium on Theory of Computing - STOC '12, 339-350. https://hdl.handle.net/10356/99006 http://hdl.handle.net/10220/12643 10.1145/2213977.2214009 en |
| spellingShingle | Guruswami, Venkatesan Xing, Chaoping Folded codes from function field towers and improved optimal rate list decoding |
| title | Folded codes from function field towers and improved optimal rate list decoding |
| title_full | Folded codes from function field towers and improved optimal rate list decoding |
| title_fullStr | Folded codes from function field towers and improved optimal rate list decoding |
| title_full_unstemmed | Folded codes from function field towers and improved optimal rate list decoding |
| title_short | Folded codes from function field towers and improved optimal rate list decoding |
| title_sort | folded codes from function field towers and improved optimal rate list decoding |
| url | https://hdl.handle.net/10356/99006 http://hdl.handle.net/10220/12643 |
| work_keys_str_mv | AT guruswamivenkatesan foldedcodesfromfunctionfieldtowersandimprovedoptimalratelistdecoding AT xingchaoping foldedcodesfromfunctionfieldtowersandimprovedoptimalratelistdecoding |