You are looking at a specific version 20140703:180838 of this paper.
See the latest version.
Paper 2014/520
On powers of codes
Ignacio Cascudo and Ronald Cramer and Diego Mirandola and Gilles Zémor
Abstract
Given a linear code $C$, one can define the $d$-th 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 $\frac{1}{2}k^2$ or smaller. 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.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Error-correcting codes
- Contact author(s)
- diego @ cwi nl
- History
- 2015-01-14: last of 2 revisions
- 2014-07-03: received
- See all versions
- Short URL
- https://ia.cr/2014/520
- License
-
CC BY