article · 1999

On Sparse Parity Check Matrices

Hanno Lefmann, Pavel Pudlák, Petr Savick&apos;y

Cited by 0Abstract and details only

Abstract

We consider the extremal problem to determine the maximal number N(m; k; r) of columns of a 0-1-matrix with m rows and at most r ones in each column such that each k columns are linearly independent modulo 2. For each fixed k 1 and r 1, we shall prove a probabilistic lower bound N(m; k; r) = \\Omega\\Gamma m kr=2(k\\Gamma1) ); for k a power of 2, we prove an upper bound N(m; k; r) = O(m dkr=(k\\Gamma1)e=2 ) which matches the lower bound for infinitely many values of r. We give some explicit constructions. 1 Introduction We shall consider matrices M over the two-element field GF 2 . If each k column vectors of M are linearly independent, we say that the columns are k-wise independent. By a (k; r)-matrix we mean a matrix, where the column vectors are k-wise independent and each column contains at most r ones. We denote by N(m; k; r) the maximal number of columns in a (k; r)-matrix with m rows. The aim of this paper is to give estimates on the growth of the function N(m; k; r). Matric...

Cite this paper

APA 7

Lefmann, H., Pudlák, P., & Savick&apos;y, P. (1999). On Sparse Parity Check Matrices.

MLA 9

Lefmann, Hanno, et al. “On Sparse Parity Check Matrices.” 1999.

Chicago

Lefmann, Hanno, Pavel Pudlák, and Petr Savick&apos;y. 1999. “On Sparse Parity Check Matrices.”

Harvard

Lefmann, H., Pudlák, P. and Savick&apos;y, P. (1999) ‘On Sparse Parity Check Matrices’.

BibTeX

@article{lefmann1999sparse,
  title = {{On Sparse Parity Check Matrices}},
  author = {Lefmann, Hanno and Pudlák, Pavel and Savick&amp;apos;y, Petr},
  year = {1999}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.