TY - GEN
T1 - It'll probably work out
T2 - 6th Conference on Innovations in Theoretical Computer Science, ITCS 2015
AU - Operations, Random
AU - Rudra, Atri
AU - Wootters, Mary
N1 - Publisher Copyright:
Copyright © 2015 ACM.
PY - 2015/1/11
Y1 - 2015/1/11
N2 - In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code. The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural transformations on codes, such as puncturing, folding, and taking subcodes; we show that many such operations can improve the list-decoding properties of a code. There are two main points to this. First, our goal is to advance our (combinatorial) understanding of list-decodability, by understanding what structure (or lack thereof) is necessary to obtain it. Second, we use our more general results to obtain a few interesting corollaries for list decoding.
AB - In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code. The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural transformations on codes, such as puncturing, folding, and taking subcodes; we show that many such operations can improve the list-decoding properties of a code. There are two main points to this. First, our goal is to advance our (combinatorial) understanding of list-decodability, by understanding what structure (or lack thereof) is necessary to obtain it. Second, we use our more general results to obtain a few interesting corollaries for list decoding.
KW - List decoding
KW - Random codes
UR - https://www.scopus.com/pages/publications/84922207909
U2 - 10.1145/2688073.2688092
DO - 10.1145/2688073.2688092
M3 - Conference contribution
AN - SCOPUS:84922207909
T3 - ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
SP - 287
EP - 296
BT - ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PB - Association for Computing Machinery, Inc
Y2 - 11 January 2015 through 13 January 2015
ER -