Speaker: Per Austrin Courant Institute of Mathematical Sciences New York University
Title: Randomly Supported Independence and Resistance
Abstract: Motivated by applications to approximability of constraint
satisfaction problems, we study questions of the following flavor:
given a random subset X of [q]^n, what is the probability that there
exists a kwise independent distribution supported on X?
We show that there are constants c_{q,k} such that, with high
probability, a uniformly random set of [c_{q,k} n^k log(n^k)] points
from [q]^n can support a kwise independent distribution, and that
this is sharp up to the logarithmic factor and the exact value of
c_{q,k}. For the case k=2, we are able to remove the logarithmic
factor and show that, with high probability, a uniformly random set of
[c_{q,2} n^k] points from [q]^n can support a pairwise independent
distribution. Finally, we show that there are other constants
c'_{q,k}>0 such that every subset of [q]^n with size at least
q^n(1c'_{q,k}) can support a kwise independent distribution.
Joint work with Johan Hastad
