Jacques Verstraete : On k-wise independent sets of vectors

Posted by Emily Dumas , part of the Departmental Colloquium.

At

April 8, 2011, 3 p.m.

In

SEO 636

Abstract

If V is a vector space over a finite field F, then a set X of vectors of V is "k-wise independent" if no set of at most k vectors from X is linearly dependent. In this talk I will discuss the problem of determining the maximum size f(n,k,r) of a k-wise independent set of vectors of Hamming weight r in a vector space of dimension n over F. Three simple examples in coding theory, derandomization and the satisfiability problem will be given to motivate this problem. Following this, a sketch of the proof due to the author and Naor determining the asymptotic value of log f(n,k,r) as n and k tend to infinity. In words, this guarantees a constant size linear dependency in any set of vectors of weight at most r of size roughly larger than the square root of the Hamming ball of radius r. Using this result, we answer a question of Erdos, Sos and Sarkozy in combinatorial number theory. We close with three open questions. In part joint work with Assaf Naor