2015-03-01
Squares of random linear codes
Publication
Publication
IEEE Transactions on Information Theory , Volume 61 - Issue 3 p. 1159- 1173
Given a linear code C, one can define the dth power of C as the span of all componentwise products of d elements of C. A power of C may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code typically fill the whole space? We give a positive answer, for codes of dimension k and length roughly (1/2)k2 or smaller. Moreover, the convergence speed is exponential if the difference k(k+1)/2-n is at least linear in k. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.
Additional Metadata | |
---|---|
, , , | |
doi.org/10.1109/TIT.2015.2393251 | |
IEEE Transactions on Information Theory | |
Organisation | Cryptology |
Cascudo, I., Cramer, R., Mirandola, D., & Zémor, G. (2015). Squares of random linear codes. IEEE Transactions on Information Theory, 61(3), 1159–1173. doi:10.1109/TIT.2015.2393251 |