So I have this question which I can't seem to find a solution to:

Prove that if $X = (X_1, ... X_n)$ is $k$-wise uniform* and each $X_i$ is Boolean then $\left|\operatorname{Supp}(X)\right| \geq \mathbf B(\frac{k}{2}, n)$, where $\mathbf B(r, n)$ is the number of words of weight at most $r$.

$*$ Where $k$-wise uniform means that, for each subset $S=\{i_1,\dots, i_s\}\subseteq [n]$ of size $s\leq k$, the distribution of $(X_{i_1},\dots,X_{i_s})$ is uniform.

  • $\begingroup$ Isn't the constant distribution $\delta_{1^n}$ (i.e., $X_i = 1$ a.s. for every $i\in[n]$) $k$-wise independent for every $1\leq k\leq n$? $\endgroup$ – Clement C. Mar 23 '18 at 10:29
  • $\begingroup$ no, it is not even 1-wise independent, k-wise independent means that if we look at a subset (every subset) of length k it will look uniform. $\endgroup$ – Itaysason Mar 24 '18 at 10:47
  • $\begingroup$ That's only one of the possible definitions. One of the standard ones defines it as "every subset of at most k of the variables is mutually independent". (With yours, pairwise and 2-wise do not coincide.) $\endgroup$ – Clement C. Mar 24 '18 at 13:59
  • 3
    $\begingroup$ For this question, I recommend using the term "k-wise uniform" instead of "k-wise independent". $\endgroup$ – Ravi Boppana Mar 24 '18 at 16:23
  • $\begingroup$ @RaviBoppana and Itaysason: I have edited the OP that way, to make it clear the assumption implies uniformity. $\endgroup$ – Clement C. Mar 25 '18 at 16:51

I believe this question was answered positively in three independent papers:

C. R. Rao (1947), "Factorial experiments derivable from combinatorial arrangements of arrays", Journal of the Royal Statistical Society 9:1, 128-139.

B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky (1985), "The bit extraction problem or t-resilient functions", 26th IEEE Symposium on Foundations of Computer Science, 396-407.

N. Alon, L. Babai, and A. Itai (1986), "A fast and simple randomized algorithm for the maximal independent set problem", Journal of Algorithms 7:4, 567-583.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.