TY - GEN
T1 - Improved bounds on the size of sparse parity check matrices
AU - Naor, Assaf
AU - Verstraete, Jacques
PY - 2005/12/1
Y1 - 2005/12/1
N2 - Let Ndouble-struck F sign(n, k, r) denote the maximum number of columns in an n-row matrix with entries in a finite field double-struck F sign in which each column has at most r nonzero entries and every k columns are linearly independent over double-struck F sign. Such sparse parity check matrices are fundamental tools in coding theory, derandomization and complexity theory. We obtain near-optimal theoretical upper bounds for N double-struck F sign(n, k, r) in the important case k > r, i.e. when the number of correctible errors is greater than the weight. Namely, we show that Ndouble-struck F sign(n, k, r) = O(nr/2+4r/3k). The best known (probabilistic) lower bound is N double-struck F sign(n, k, r) = Ω(nr/2+r/2k-2), while the best known upper bound in the case k > r was for k a power of 2, in which case Ndouble-struck F sign(n, k, r) = Ω(n r/2+1/2). Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependences in large sets of sparse vectors. In the full version of this paper we present additional applications of this method to problems in combinatorial number theory.
AB - Let Ndouble-struck F sign(n, k, r) denote the maximum number of columns in an n-row matrix with entries in a finite field double-struck F sign in which each column has at most r nonzero entries and every k columns are linearly independent over double-struck F sign. Such sparse parity check matrices are fundamental tools in coding theory, derandomization and complexity theory. We obtain near-optimal theoretical upper bounds for N double-struck F sign(n, k, r) in the important case k > r, i.e. when the number of correctible errors is greater than the weight. Namely, we show that Ndouble-struck F sign(n, k, r) = O(nr/2+4r/3k). The best known (probabilistic) lower bound is N double-struck F sign(n, k, r) = Ω(nr/2+r/2k-2), while the best known upper bound in the case k > r was for k a power of 2, in which case Ndouble-struck F sign(n, k, r) = Ω(n r/2+1/2). Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependences in large sets of sparse vectors. In the full version of this paper we present additional applications of this method to problems in combinatorial number theory.
UR - http://www.scopus.com/inward/record.url?scp=33749425389&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33749425389&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2005.1523645
DO - 10.1109/ISIT.2005.1523645
M3 - Conference contribution
AN - SCOPUS:33749425389
SN - 0780391519
SN - 9780780391512
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1749
EP - 1752
BT - Proceedings of the 2005 IEEE International Symposium on Information Theory, ISIT 05
T2 - 2005 IEEE International Symposium on Information Theory, ISIT 05
Y2 - 4 September 2005 through 9 September 2005
ER -