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?
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→{0,1}n with a corresponding decoding function d:{0,1}n→{0,1}k, and assume that m≪2k/2 .
For any function g:{0,1}k→{0,1} we can define f=g∘d. We then choose g randomly from the 22k such functions. We want to code to be such that for random x∈{0,1}n and random S⊂{1,…,n} the information (xS,S} is enough to deduce d(x)∈{0,1}k, with high probability. Then each Yi would give Bob one bit of information about g (its value at the point d(xi)) and hence one bit about f. Here we use the assumption m≪2k/2 to avoid collisions d(xi)=d(xj).
Unfortunately, this argument does not work. The issue is that x∈{0,1}n is chosen at random, instead of as an encoding c(x′) 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 (xS,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?
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?
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→{0,1}n with a corresponding decoding function d:{0,1}n→{0,1}k, and assume that m≪2k/2 .
For any function g:{0,1}k→{0,1} we can define f=g∘d. We then choose g randomly from the 22k such functions. We want to code to be such that for random x∈{0,1}n and random S⊂{1,…,n} the information (xS,S} is enough to deduce d(x)∈{0,1}k, with high probability. Then each Yi would give Bob one bit of information about g (its value at the point d(xi)) and hence one bit about f. Here we use the assumption m≪2k/2 to avoid collisions d(xi)=d(xj).
Unfortunately, this argument does not work. The issue is that x∈{0,1}n is chosen at random, instead of as an encoding c(x′) 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 (xS,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?