Improved bounds on the size of sparse parity check matrices
Assaf Naor, Jacques Verstraëte · 2005
Let NF;(n, k, r) denote the maximum number of columns in an n-row matrix with entries in a finite field F in which each column has at most r nonzero entries and every k columns are linearly independent over F. Such sparse parity check matrices are fundamental tools in coding theory, derandomization and complexity theory. We obtain near-optimal theoretical upper bounds for NF(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 NF(n, k, r) = O(n(r/2)+(4r/3k)). The best known (probabilistic) lower bound is NF(n, k, r) = Omega(n(r/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 NF(n, k, r) = Omega(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