Randomly Supported Independence and Resistance
Per Austrin, Johan Håstad · SIAM Journal on Computing · 2011
We prove that for any positive integers q and k there is a constant $c_{q,k}$ such that a uniformly random set of $c_{q,k}n^k\log n$ vectors in $[q]^n$ with high probability supports a balanced k-wise independent distribution. In the case of $k\leq2$ a more elaborate argument gives the stronger bound, $c_{q,k}n^k$. Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting $c_{q,2}t^2$ input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, $c_{q,k}'$, such that a randomly selected set of cardinality $c_{q,k}'n^k$ points is unlikely to support a balanced k-wise independent distribution and, for some $c>0$, a random predicate accepting $ct^2/\log t$ input vectors is nontrivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the unique games conjecture, any predicate on t Boolean inputs accepting at least $(32/33)\cdot2^t$ inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.