$500 Bounty/Prize Problem: Channel Capacity Using "Insensitive" Functions

Here's an argument that I think works in the limit where $m\to \infty$. For very large $m$, each subset $S\subseteq \left[n\right]$ of size $s$ will occur many times as an $S_i$. Moreover, for each set of coodinate values $x_S:=(x_j{)}_{j\in S}$, there will be many $x^i$ such that $S_i=S$ and $x_S^i=x_S$. Therefore, using the law of large numbers for any subset $S\subseteq \left[n\right]$ of size $s$ and any set of coordinate values $x_S$, Bob can infer $N(x_S,f):=\#\{x^{\prime }\in \{0,1{\}}^n:x_S^{\prime }=x_S\text{and}f\left(x^{\prime }\right)=1\}$, i.e. the number of inputs $x^{\prime }$ that agree with $x_S$ at the coordinates indexed by $S$ for which $f\left(x^{\prime }\right)=1$. Additionally, the random variable $Y$ contains no other information about $f$ that is not contained in this set of statistics.

Given a function $f:\{0,1{\}}^n\to \{0,1\}$, let $F\left(f\right)$ denote the set of all functions $f^{\prime }$ such that for each subset $S\subseteq \left[n\right]$ of size $s$ and each set of coordinate values $x_S$,  $N(x_S,f)=N(x_S,f^{\prime })$. The argument of the previous paragraph then implies that upon observing $Y$ Bob can deduce the equivalence class $F\left(f\right)$, but no other information about $f$ from $Y$.

If we have a random variable $X$ and we define another random variable $Y$ as a deterministic function $Y\left(X\right)$, then it is easy to show that the set of distributions of $X$ which maximize the mutual information between $Y$ and $X$ are precisely those for which $Y$ has a uniform distribution. Applying this to the above setup, we see that the distributions over $f$ which maximize the channel capacity are those for which $F\left(f\right)$ is uniformly distributed over all the values that it can take.

If we suppose in addition that $f$ has the maximum entropy distribution subject to this constraint, we find that:

$P\left[f\right]\propto 1/\left(\#\right\{f^{\prime }:N(x_S,f)=N(x_S,f^{\prime })\text{for all}S\subseteq \left[n\right],x_S\in \{0,1{\}}^S\})$.

Intuitively, this says that the probability of a given function $f$ is inversely proportional to the number of other functions $f^{\prime }$ that have the same number of ones on every hyperplane defined by fixing a set of some $s$ coordinates $x_S$. This seems to correspond roughly to sensitivity: we intuitively expect there to be a lot of such functions $f^{\prime }$ when the number of ones that $f$ outputs on most hyperplanes is approximately half of the number of total points on that hyperplane, and saying that a function's output is approximately half ones and half zeros on a given hyperplane is roughly saying that $f$ is sensitive to the remaining unspecified coordinates.

It's not obvious to me that the above expression for $P\left[f\right]$ is feasible to compute in practice, but I think it is fairly naturally interpretable.

The key reason the problem is tractable in the case $m\to \infty$ is that the law of large numbers means the probabilities wash out and we get an essentially deterministic problem. In the case where $m$ is finite, this won't happen and in particular I expect you'll run into complications that arise from interaction terms where the method for combining the information from two observations $Y_i$ and $Y_j$ with $S_i\ne S_j$ is not clean.

I expect you're more likely to end up with a tractable solution if you rephrase the problem statement slightly so that the subsets of inputs over which you're agregating outputs when observed (in the case above, these subsets are the hyperplanes defined by the coordinates $x_S$) are disjoint or overlapping. (For example, taking all the $S_i$ to be random but equal would ensure this.) It strikes me that there might be a formulation like this that still captures the key features of the problem you're interested in, but I've not thought about this in detail.

I'm interested in characterizing functions which are "insensitive" to subsets of their input variables, especially in high-dimensional spaces.

There's a field called "Analysis of boolean functions" (essentially Fourier analysis of functions $f:\{0,1{\}}^n\to \{0,1\}$) that seems relevant to this question and perhaps to your specific problem statement. In particular, the notion of "total influence" of a boolean function is meant to capture its sensitivity (e.g. the XOR function on all inputs has maximal total influence). This is the standard reference, see section 2.3 for total influence. Boolean functions with low influence (i.e. "insensitive" functions) are an important topic in this field, so I expect there are some relevant results (see e.g. tribes functions and the KKL theorem, though those specifically address a somewhat different question than your problem statement).

I'm not sure whether this is helpful, but this reminds me of Error Correction Codes, a way of transmitting information through a noisy channel that trades bandwidth for reliability by encoding the intended message redundantly.

An explanation that I found helpful when learning about them was that you can think of a packet of N bits as specifying one corner of an N-dimensional hypercube, and an ECC as saying that you'll only intentionally transmit certain corners and not others.  If you select a subset of corners such that no allowed corner is adjacent to any other, then a 1-bit error will always land you on a disallowed corner, so the receiver will know an error occurred.  If all allowed corners are some distance from all other allowed corners, then you can guess the most likely intended corner based on distance from the corner received.

An XOR of all bits is maximally noisy because every corner with a value of "1" is surrounded by corners with a value of "0" and vice-versa.  The corners corresponding to a given answer are maximally dispersed, so every error changes the result.

The inverse of that strategy is to designate exactly-opposite corners as "0" and "1", and then map all the remaining corners by which of those they're closer to.  In other words, slice the hypercube in half, and then assign the same value to all corners in a given half.  (The "majority of bits" function does exactly this.)

I don't think I can personally convert that into an answer to the stated problem, but maybe it will give someone else a thread to pull on?

Here's a possible construction, building on Dweomite's suggestion to use error correction codes. We treat the selection of the random variables that Bob sees as a binary erasure channel with probability $\frac{n-s}{n}$ of erasure. Choose some error-correcting code for the BEC. Now, Alice constructs a function in the following way: For each input $x$, randomly choose a subset $S$ of size $s$. Apply the decoder for our error-correcting code to the subset; we obtain some string $y$^[1]. Alice chooses a function $f$ which is constant on pre-images of a given string $y$ under this mapping. She could either choose such an $f$ uniformly at random, or possibly treat the selection of inputs as another binary erasure channel(on sequences of 1s and 0s indexed by the string $y$) and use another error-correcting code.

sampled uniformly and independently

🤔 I don't believe this definition fits the "apple" example - uniform samples from a concept space of "apple or not apple" would NEVER™ contain any positive example (almost everything is "not apple")... or what assumption am I missing that would make the relative target volume more than ~zero (for high n)?

Bob will observe a highly optimized set of Y, carefully selected by Alice, so the corresponding inputs will be Vastly correlated and interdependent at least for the positive examples (centeroid first, dynamically selected for error-correction later 🤷‍♀️), not at all selected by Nature, right?

I'm fairly sure you can get a result something like "it's not necessary to put positive probability mass on two different functions that can't be distinguished by observing only s bits", so some functions can get zero probability, e.g. the XOR of all combinations of at least s+1 bits.

edit: The proof is easy. Let $f_1$, $f_2$ be two such indistinguishable functions that you place positive probability on, F be a random variable for the function, and F' be F but with all probability mass for $f_2$ replaced by $f_1$. Then $P\left(Y|F\right)=P\left(Y|F^{\prime }\right)$. But this means $H\left(Y|F\right)=H\left(Y|F^{\prime }\right)$ and so $I(Y,F)=H\left(Y\right)-H\left(Y|F\right)=H\left(Y\right)-H(Y,F^{\prime })=I(Y,F^{\prime }).$ You don't lose any channel capacity switching to $F^{\prime }.$

This question is non-trivial even for $s=0$. Here it becomes: let Alice choose a probability $p$ (which has to be on the form $p=\frac{k}{2^n}$ but this is irrelevant for large $n$) and Bob observes the binomially distributed number $B(m,p)$. With which distribution should Alice choose $p$ to maximize the capacity of this channel.