Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common.

In the paper "The space complexity of approximating the frequency moments" by Alon et al. they say that the existence of such a familty $\mathcal{G}$ follows from basic results in coding theory.

Can anyone give a proof of the existence or provide any pointers to the relevant results in coding theory that this follows from?

  • 3
    $\begingroup$ A proof sketch is given in Nisan & Wigderson, Hardness vs. randomness, Lemma 2.6. $\endgroup$ Nov 24 at 15:06
  • 2
    $\begingroup$ Doesn't this follow by a standard kind of probabilistic construction? Just choose an appropriate number of random subsets of size $n/4$.. Then show that the expected number of pairs that have more than $n/8$ elements in common is less than 1... $\endgroup$
    – Neal Young
    Nov 25 at 3:47
  • 1
    $\begingroup$ Not a full answer, but the reduction is to represent each subset as a binary string of length $n$, with a one in the $i$th position iff the $i$th element is in the subset. The family $\mathcal{G}$ is an error-correcting code. With $x$ elements in common, the Hamming distance is $n/2-2x$. $\endgroup$
    – usul
    Nov 25 at 22:08


Your Answer

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

Browse other questions tagged or ask your own question.