Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RECONSTRUCTING GRAPHS FROM QUERIES:
Reports tagged with Reconstructing Graphs from Queries:
TR09-067 | 18th August 2009
Hanna Mazzawi, Nader Bshouty

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