Title: Randomly Supported Independence
Speaker: Per Austrin, KTH, Stockholm
(Joint work with Johan Håstad)
We study questions of the following flavor: given a random subset $S$
of $[q]^n$, what is the probability that there exists a $k$-wise
independent distribution supported on $S$? These questions are
motivated by the importance of $k$-wise independence in general, and
by applications to hardness of approximation in particular.
We prove that, with high probability, $\poly(q) n2$ random points in
$[q]^n$ can support a pairwise independent distribution. Then, again
with high probability, we show that $(\poly(q) n)^t \log(n^t)$ random
points in $[q]^n$ can support a $t$-wise independent distribution.
Finally, we show that every subset of $[q]^n$ with size at least
$q^n(1-\poly(q)^{-t})$ can support a $t$-wise independent
distribution.