Departmental Colloquium
Jacques Verstraete
UCSD
On k-wise independent sets of vectors
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
Friday April 8, 2011 at 3:00 PM in SEO 636