Analogue of $k$-wise independence for other distributions than uniform

Question

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?

Answer 1

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.

Answer 2

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