TY - GEN
T1 - Average-radius list-recoverability of random linear codes
AU - Rudra, Atri
AU - Wootters, Mary
N1 - Publisher Copyright:
© Copyright 2018 by SIAM.
PY - 2018
Y1 - 2018
N2 - We analyze the list-decodability, and related notions, of random linear codes. This has been studied extensively before: there are many different parameter regimes and many different variants. Previous works have used complementary styles of arguments|which each work in their own parameter regimes but not in others| and moreover have left some gaps in our understanding of the list-decodability of random linear codes. In particular, none of these arguments work well for listrecovery, a generalization of list-decoding that has been useful in a variety of settings. In this work, we present a new approach, which works across parameter regimes and further generalizes to list-recovery. In particular, our argument provides better results for list-decoding and list-recovery over large fields; improved (quasipolynomial) list sizees for high-rate list-recovery of random linear codes; improved algorithmic results for list-decoding; and optimal average-radius list-decoding over constant-sized alphabets.
AB - We analyze the list-decodability, and related notions, of random linear codes. This has been studied extensively before: there are many different parameter regimes and many different variants. Previous works have used complementary styles of arguments|which each work in their own parameter regimes but not in others| and moreover have left some gaps in our understanding of the list-decodability of random linear codes. In particular, none of these arguments work well for listrecovery, a generalization of list-decoding that has been useful in a variety of settings. In this work, we present a new approach, which works across parameter regimes and further generalizes to list-recovery. In particular, our argument provides better results for list-decoding and list-recovery over large fields; improved (quasipolynomial) list sizees for high-rate list-recovery of random linear codes; improved algorithmic results for list-decoding; and optimal average-radius list-decoding over constant-sized alphabets.
UR - https://www.scopus.com/pages/publications/85045579309
U2 - 10.1137/1.9781611975031.42
DO - 10.1137/1.9781611975031.42
M3 - Conference contribution
AN - SCOPUS:85045579309
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 644
EP - 662
BT - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Czumaj, Artur
PB - Association for Computing Machinery
T2 - 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -