Randomly supported independence and resistance

by Per Austrin and Johan Hastad

Oded's comments

The actual technical core of this paper is a study of the size of random sets of $n$-bit strings that (w.h.p.) support a $k$-wise independent distribution over $n$-bit strings, where a set $S$ supports a $k$-wise independent distribution if there exists such a distribution whose support is coantianed in $S$. Interestingly, this happens at size $\tildeO(n^k)$, and this result is essentially tight. The paper also studies the size for which every set supports some $k$-wise independent distribution, which is $(1-Omega(1)^k) 2^n$. My feeling is that these results may be useful in the context of proving lower bounds (e.g., for property testing). The application to approximation resistence follows via a result of Austrin and Mossel (CCC'08).

The original abstract

We prove that for any positive integer $k$, there is a constant $c_k$ such that a randomly selected set of $c_k n^k \log n$ Boolean vectors with high probability supports a balanced $k$-wise independent distribution. In the case of $k \leq 2$ a more elaborate argument gives the stronger bound $c_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_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_k'$, such that a randomly selected set of cardinality $c_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 non-trivially 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$ bits accepting at least $(32/33) \cdot 2^t$ inputs is approximation resistant. Essentially all results extend from the Boolean domain to larger finite domains.


Back to list of Oded's choices.