Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMBINATORIAL SEARCH:
Reports tagged with Combinatorial search:
TR09-067 | 18th August 2009

#### On Parity Check $(0,1)$-Matrix over $Z_p$

Revisions: 1

We prove that for every prime $p$ there exists a $(0,1)$-matrix
$M$ of size $t_p(n,m)\times n$ where
$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every
$m$ columns of $M$ are linearly independent over $\Z_p$, the field
of integers modulo $p$ (and therefore over any field of
characteristic $p$ and over the real ... more >>>

ISSN 1433-8092 | Imprint