<p>I met once a similar notion to what you want in one paper by <a href="https://eprint.iacr.org/2012/076" rel="nofollow noreferrer">Mark Zhandry's paper</a> under the name <em><span class="math-container">$k$</span>-wise equivalent</em>. I cannot find further references or pointers from that paper, but I think this name nicely describes your <em>something</em>.</p>
<p>Concretely, the original definition in the paper is about the distributions over the functions <span class="math-container">$f: X\rightarrow Y$</span>, and define the size-<span class="math-container">$k$</span> marginal by its marginal distribution for any size-<span class="math-container">$k$</span> subset <span class="math-container">$W$</span> of <span class="math-container">$X$</span>. The notion <em><span class="math-container">$k$</span>-wise equivalence</em> is defined accordingly, that is, two distributions are identical on any <span class="math-container">$k$</span>-marginal.</p>
<p>It is not directly addressing your main question, but we can say that your desired distribution is <span class="math-container">$k$</span>-wise equivalent to the uniform random permutation. It also, unfortunately, does not give any efficient construction for equivalent distribution as well.</p>

CC BY-SA 4.0
2021-01-02T12:20:38.870Z
2021-01-02T12:20:38.870Z
Hhan
<p>Here is an approach/related concept for the case of interest mentioned in the question,</p>

<blockquote>
  <p><span class="math-container">$D$</span> being the distribution of the <span class="math-container">$n$</span> bits indicators obtained when choosing [uniformly at random] a subset of <span class="math-container">$[n]$</span> of size exactly <span class="math-container">$n/2$</span>.</p>
</blockquote>

<p>Let more generally <span class="math-container">$m$</span> be any integer dividing <span class="math-container">$n$</span>, and <span class="math-container">$D_{n,m}$</span> be the uniform distribution over all <span class="math-container">$m$</span>-equipartitions of <span class="math-container">$[n]$</span>. (The above corresponds to <span class="math-container">$m=2$</span>.)</p>

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

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

CC BY-SA 4.0
2019-04-11T20:59:44.200Z
Hi Clement, just thought that this work of Alon and Lovett might be relevant: https://www.math.ias.edu/csdm/files/10-11/nalon_almost_kwise_vs_kwise_independent_permutations.pdf
Alex Golovnev
CC BY-SA 4.0
2019-04-12T00:24:11.320Z
@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)?
Clement C.
CC BY-SA 4.0
2019-04-11T10:51:42.060Z
2019-04-11T11:04:49.210Z
2019-04-11T11:04:49.210Z
Clement C.
<p><em>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.</em></p>

<p>Let <span class="math-container">$D$</span> be a fixed distribution over <span class="math-container">$\{0,1\}^n$</span>, and <span class="math-container">$1\leq k\leq n$</span> a fixed integer. A random variable <span class="math-container">$X$</span> over <span class="math-container">$\{0,1\}^n$</span> is said to be <em><span class="math-container">$(k,D)$</span>-something</em> if all size-<span class="math-container">$\ell$</span> marginals of <span class="math-container">$X$</span>, for <span class="math-container">$\ell\leq k$</span>, match those of <span class="math-container">$D$</span>.</p>

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

<blockquote>
  <p>Does <em>something</em> have a name?</p>
</blockquote>

CC BY-SA 4.0
2019-04-11T06:56:19.343Z
@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](https://people.seas.harvard.edu/~salil/pseudorandomness/), or [most lecture notes (section 2)](http://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec7.pdf), evn [...]
Clement C.
CC BY-SA 4.0
2019-04-11T06:56:29.813Z
[...] [a search](https://cstheory.stackexchange.com/questions/31648/can-we-construct-a-k-wise-independent-permutation-on-n-using-only-constant-tim) on this [very website](https://cstheory.stackexchange.com/questions/30716/k-wise-independence-vs-min-entropy). Hence my conflating the two in the question... Updating the question to make that clear.
Clement C.
<reference-request><k-wise-independence>
Analogue of $k$-wise independence for other distributions than uniform
Clement C.
# Analogue of $k$-wise independence for other distributions than uniform

(Asked by: username_0 on 2019-04-09)

*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?

**Tags:** reference-request, k-wise-independence

> **Comments:**
> **username_0**: @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](https://people.seas.harvard.edu/~salil/pseudorandomness/), or [most lecture notes (section 2)](http://sites.math.rutgers.edu/~sk1233/courses/topics-S13/lec7.pdf), evn [...]  
> **username_0**: [...] [a search](https://cstheory.stackexchange.com/questions/31648/can-we-construct-a-k-wise-independent-permutation-on-n-using-only-constant-tim) on this [very website](https://cstheory.stackexchange.com/questions/30716/k-wise-independence-vs-min-entropy). Hence my conflating the two in the question... Updating the question to make that clear.  

---

## 2 answers

### Answer by username_1 on 2021-01-02. Score: 3

I met once a similar notion to what you want in one paper by [Mark Zhandry's paper](https://eprint.iacr.org/2012/076) 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 by username_0 on 2019-04-11. Score: 0

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

> **Comments:**
> **username_2**: Hi Clement, just thought that this work of Alon and Lovett might be relevant: https://www.math.ias.edu/csdm/files/10-11/nalon_almost_kwise_vs_kwise_independent_permutations.pdf  
> **username_0**: @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)?  

---

