5
$\begingroup$

I am looking for the name of the following notion (in order to look it up for myself), and possibly pointers to the corresponding literature.

Let $D$ be a fixed distribution over $\{0,1\}^n$, and $1\leq k\leq n$ a fixed integer. A random variable $X$ over $\{0,1\}^n$ is said to be $(k,D)$-something if all size-$\ell$ marginals of $X$, for $\ell\leq k$, match those of $D$.

In particular, for $D$ product distribution (and, in most derandomization literature I have seen, actually for $D$ uniform), this is $k$-wise independence. I am looking for $D$ non-uniform, however -- for instance, $D$ being the distribution of the $n$ bits indicators obtained when choosing a subset of $[n]$ of size exactly $n/2$.

Does something have a name?

$\endgroup$
  • $\begingroup$ Isn't this just "k-wise independence"?! $\endgroup$ – Jeffε Apr 10 at 21:01
  • $\begingroup$ @Jeffε well, no. Is it? First, $k$-wise independence" is basically used for "$k$-wise uniform independence*" most of the time. This notwithstanding, as my last example in particular illustrates, I am considering distributions where the coordinates are not necessarily independent. $\endgroup$ – Clement C. Apr 10 at 23:20
  • $\begingroup$ Sorry, I see the difference now, but no, [adjective] independence does not imply anything about uniformity. $\endgroup$ – Jeffε Apr 11 at 5:15
  • $\begingroup$ @Jeffε Sorry, I should have been more precise. It's true that there ins no implication of uniformity in general; however, for derandomization (which is my end goal here), I am under the impression that, by and large, "$k$-wise independent" and "$k wise independent uniform" are used interchangeably. See, e.g., a search for "derandomization k-wise" on Google, or for instance Chapater 3, Definition 3.21 in this monongraph, or most lecture notes (section 2), evn [...] $\endgroup$ – Clement C. Apr 11 at 6:56
  • $\begingroup$ [...] a search on this very website. Hence my conflating the two in the question... Updating the question to make that clear. $\endgroup$ – Clement C. Apr 11 at 6:56
0
$\begingroup$

Here is an approach/related concept for the case of interest mentioned in the question,

$D$ being the distribution of the $n$ bits indicators obtained when choosing [uniformly at random] a subset of $[n]$ of size exactly $n/2$.

Let more generally $m$ be any integer dividing $n$, and $D_{n,m}$ be the uniform distribution over all $m$-equipartitions of $[n]$. (The above corresponds to $m=2$.)

Since drawing such an $m$-equipartition is equivalent to (i) taking a deterministic partition of that sort over $[n]$ and (ii) applying it to a u.a.r. permutation of $[n]$, any family $\mathcal{C}$ of $k$-wise independent partitions of $[n]$ yields a $(k,D_{n,m})$-something random variable $X$ samplable with $\log|\mathcal{C}|$ u.a.r. bits.

Unfortunately, no exact (non-trivial) family of $k$-wise independent permutations is known to exist for $k\geq 4$, even non-constructively, as far as I know. So then one would have to settle with $k$-wise almost independent permutations (and see how the approximation propagates).

$\endgroup$
  • $\begingroup$ Hi Clement, just thought that this work of Alon and Lovett might be relevant: math.ias.edu/csdm/files/10-11/… $\endgroup$ – Alex Golovnev Apr 11 at 20:59
  • $\begingroup$ @AlexGolovnev Thanks! I saw that paper... They do only provide results for distributions over almost independent permutation families and distributions over independent ones, though, right? So that it's unclear how to sample from them with few bits as the distributions are not necessarily uniform (or did I miss something)? $\endgroup$ – Clement C. Apr 12 at 0:24

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.