Randomly Supported Independence and Resistance

We prove that for any positive integers q and k there is a constant cq,k such that a uniformly random set of cq,knᵏlog n vectors in [q]ⁿ with high probability supports a balanced k-wise independent distribution. In the case of k≤2 a more elaborate argument gives the stronger bound, cq,knᵏ. Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting cq,2t² 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, cq,k', such that a randomly selected set of cardinality cq,k'nᵏ points is unlikely to support a balanced k-wise independent distribution and, for some $c>0$, a random predicate accepting ct²/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)·2ᵗ inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.