Sune comments on $500 Bounty/​Prize Problem: Channel Capacity Using “Insensitive” Functions

[Sune]

I tried and failed to formalize this. Let me sketch the argument, to show where I ran into problems.

Considering a code $c:\{0,1{\}}^k\to \{0,1{\}}^n$ with a corresponding decoding function $d:\{0,1{\}}^n\to \{0,1{\}}^k$, and assume that $m\ll 2^{k/2}$ .

For any function $g:\{0,1{\}}^k\to \{0,1\}$ we can define $f=g\circ d$. We then choose $g$ randomly from the $2^{2^k}$ such functions. We want to code to be such that for random $x\in \{0,1{\}}^n$ and random $S\subset \{1,\dots ,n\}$ the information $(x_S,S\}$ is enough to deduce $d\left(x\right)\in \{0,1{\}}^k$, with high probability. Then each $Y_i$ would give Bob one bit of information about $g$ (its value at the point $d\left(x_i\right)$) and hence one bit about $f$. Here we use the assumption $m\ll 2^{k/2}$ to avoid collisions $d\left(x_i\right)=d\left(x_j\right)$.

Unfortunately, this argument does not work. The issue is that $x\in \{0,1{\}}^n$ is chosen at random, instead of as an encoding $c\left(x^{\prime }\right)$ of a message. Because of this, we should not expect $x$ to be close to a valid code, so we should not expect there to be a decoding method that will give consistent decodings of $(x_S,S)$ for different values of $S$.

It is not clear to me if this is a bug in the solution or a bug in the problem! The world is not random, so why do we want $x$ to be uniform in $\{0,1{\}}^n$?