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.