Intersecting codes and independent families

Abstract

A binary intersecting code is a linear code with the property that any two nonzero codewords have intersecting supports. These codes appear in a wide variety of contexts and applications, e.g., multiple access, cryptography, and information theory. This paper is devoted partly to the study of intersecting codes, and partly to their use in constructing large t-independent families of binary vectors. The latter subject has by now been extensively studied and has application in VLSI testing, defect correction, E-biased probability spaces, and derandomization. By concatenation methods we construct codes with the highest known fate asymptotically. We then generalize the concept to t-wise intersecting codes: we give bounds on the achievable rate of such codes, both existential and constructive. We show how t-wise intersecting codes can be used to obtain (t+1)-independent families. With this method we obtain improved asymptotical constructions of t-independent families. Complexity issues are discussed.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>