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?

  • $\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 '19 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 '19 at 6:56

I met once a similar notion to what you want in one paper by Mark Zhandry's paper under the name $k$-wise equivalent. I cannot find further references or pointers from that paper, but I think this name nicely describes your something.

Concretely, the original definition in the paper is about the distributions over the functions $f: X\rightarrow Y$, and define the size-$k$ marginal by its marginal distribution for any size-$k$ subset $W$ of $X$. The notion $k$-wise equivalence is defined accordingly, that is, two distributions are identical on any $k$-marginal.

It is not directly addressing your main question, but we can say that your desired distribution is $k$-wise equivalent to the uniform random permutation. It also, unfortunately, does not give any efficient construction for equivalent distribution as well.


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).

  • $\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 '19 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 '19 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.