Return to Question

Let $k, n \in \mathbb{N}$, $k < (1 - \epsilon)n$ where $1 >\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that:

1. $f(a) \not= f(b)$ if $a \not=b $

2. for any $x \in \{0,1\}^n$ $V_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).

3. $f$ can be calculated fast - in polynomial(k) time

Whether there is such $f$?

UPD: $|V_x(k/2)| \approx 2^{nH((1-\epsilon)/2)}$ By properties of entropy $t: = H((1-\epsilon)/2 < 1$ $|V_x(k/2)| / |\{0,1\}^n| = 2^{tn}:2^n = 2^{(t-1)n}$. So in "random" full-sphere there $|\{0,1\}^k| \cdot 2^{(t-1)n} < 2^k \cdot 2^{(t-1)k} = 2^{tk} $ points from $Im(f)$ in case of "random" $f$

Let $k, n \in \mathbb{N}$, $k = (1 - \epsilon)n$ where $1 >\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that:

1. $f(a) \not= f(b)$ if $a \not=b $

2. for any $x \in \{0,1\}^n$ $V_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).

3. $f$ can be calculated fast - in polynomial(k) time

Whether there is such $f$?

UPD: $|V_x(k/2)| \approx 2^{nH((1-\epsilon)/2)}$ By properties of entropy $t: = H((1-\epsilon)/2 < 1$ $|V_x(k/2)| / |\{0,1\}^n| = 2^{tn}:2^n = 2^{(t-1)n}$. So in "random" full-sphere there $|\{0,1\}^k| \cdot 2^{(t-1)n} < 2^k \cdot 2^{(t-1)k} = 2^{tk} $ points from $Im(f)$ in case of "random" $f$

Let $k, n \in \mathbb{N}$, $k < (1 - \epsilon)n$ for some little $\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that:

1. $f(a) \not= f(b)$ if $a \not=b $

2. for any $x \in \{0,1\}^n$ $V_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).

3. $f$ can be calculated fast - in polynomial(k) time

Whether there is such $f$?

UPD: $|V_x(k/2)| \approx 2^{nH((1-\epsilon)/2)}$ By properties of entropy $t: = H((1-\epsilon)/2 < 1$ $|V_x(k/2)| / |\{0,1\}^n| = 2^{tn}:2^n = 2^{(t-1)n}$. So in "random" full-sphere there $|\{0,1\}^k| \cdot 2^{(t-1)n} < 2^k \cdot 2^{(t-1)k} = 2^{tk} $ points from $Im(f)$ in case of "random" $f$

Let $k, n \in \mathbb{N}$, $k < (1 - \epsilon)n$ where $1 >\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that:

1. $f(a) \not= f(b)$ if $a \not=b $

2. for any $x \in \{0,1\}^n$ $V_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).

3. $f$ can be calculated fast - in polynomial(k) time

Whether there is such $f$?

UPD: $|V_x(k/2)| \approx 2^{nH((1-\epsilon)/2)}$ By properties of entropy $t: = H((1-\epsilon)/2 < 1$ $|V_x(k/2)| / |\{0,1\}^n| = 2^{tn}:2^n = 2^{(t-1)n}$. So in "random" full-sphere there $|\{0,1\}^k| \cdot 2^{(t-1)n} < 2^k \cdot 2^{(t-1)k} = 2^{tk} $ points from $Im(f)$ in case of "random" $f$

Let $k, n \in \mathbb{N}$, $k < (1 - \epsilon)n$ for some little $\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that:

1. $f(a) \not= f(b)$ if $a \not=b $

2. for any $x \in \{0,1\}^n$ $V_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).

3. $f$ can be calculated fast - in polynomial(k) time

Whether there is such $f$?

Let $k, n \in \mathbb{N}$, $k < (1 - \epsilon)n$ for some little $\epsilon > 0$. I want to find $f: \{0,1\}^k \to \{0, 1\}^n$ such that:

1. $f(a) \not= f(b)$ if $a \not=b $

2. for any $x \in \{0,1\}^n$ $V_x(k/2) \cap Im(f) \le 2^{k(1 - \delta)}$ for some $\delta > 0$, where $V_x(k/2)$ is a full-sphere with center $x$ and radius $k/2$ (in Hamming's metric ).

3. $f$ can be calculated fast - in polynomial(k) time

Whether there is such $f$?

UPD: $|V_x(k/2)| \approx 2^{nH((1-\epsilon)/2)}$ By properties of entropy $t: = H((1-\epsilon)/2 < 1$ $|V_x(k/2)| / |\{0,1\}^n| = 2^{tn}:2^n = 2^{(t-1)n}$. So in "random" full-sphere there $|\{0,1\}^k| \cdot 2^{(t-1)n} < 2^k \cdot 2^{(t-1)k} = 2^{tk} $ points from $Im(f)$ in case of "random" $f$