Skip to content

One Flip Sends Many Bits

March 14, 2016


Another coins on a chessboard puzzle

HouYifanMauriceAshley
Cropped from Ashley’s TwiCopy source

Hou Yifan and Maurice Ashley are champions of chess in several senses. Hou just regained the Women’s World Champion title by defeating Mariya Muzychuk of Ukraine 3-0-6 in their match which ended today in Lviv. Along with her male Chinese compatriots who reign as Olympiad team champions, she headlines an extraordinary growth of the game in southeast Asia. Ashley became the first ever grandmaster to play a tournament in Jamaica where he was born and has been one of the game’s premier video commentators and ambassadors for over two decades. The past two years he teamed with entrepreneur Amy Lee of Vancouver to create and run the Millionaire Chess open tournaments in Las Vegas, to raise the professional profile of the game.

Today Ken and I present another puzzle in our “Coins on a Chessboard” series, theming it after Ashley’s “Millionaire Square” promotion.

These are exciting weeks in Chess and in Go. Besides the women’s championship match, the World Chess Federation (FIDE) Candidates’ Tournament to determine the next challenger to world champion Magnus Carlsen started Friday in Moscow. Former world champion Viswanathan Anand of India, the oldest player at 46, shares the lead with Levon Aronian of Armenia and Sergey Karjakin of Russia, each with a win and two draws, A major international Open is taking place in Reykjavik, 44 years on from the famous match between Boris Spassky and Bobby Fischer. The fifth and final game of the Go match between Google DeepMind’s AlphaGo program and world #4 Lee Sedol is starting at midnight ET; Sedol has lost the series at 3-1 down but will try to build on his Game 4 win.

Millionaire Chess brought the first ever $1,000,000 total prize fund to a long weekend of open chess. As customary at many events, the tournament is divided into sections by rating class, so that amateur players have a shot at the biggest prizes. Last October’s event introduced the “Millionaire Square” finale in which the nine section winners played a quiz-game show to give one a chance to win a separate $1M prize underwritten by the sponsors by guessing which of 64 squares it was “under.” The winner guessed c4 but it was b1. We do not know if this promotion will be brought back for the 2016 tournament at Harrah’s in Atlantic City. It gave Ken a neat way to re-phrase the puzzle from the source given by a student in my discrete math class.

chessboardcoins
src

The Puzzle

Suppose “Millionaire Square” is presented in this glitzy manner next October: A chessboard is set out with 64 golden coins bearing the Harrah’s logo (“heads”) on one side and the Millionaire Chess logo (“tails”) on the other. The prize is under one of the squares. The coins are randomly arranged heads or tails. The lucky finalist is led out from a blind never having seen the board before, picks a coin, and wins if he or she chose the right square. Like last October it’s a 1-in-64 shot.

Now suppose this is presented to the audience with extra pizzazz. A staffer comes out first, picks up one of the coins, shows both sides to the audience, and puts it back on the square. The coin is set back just like all the other coins except it might now be heads instead of tails, or tails instead of heads. Is this secure?

Suppose the staffer knows the right square and wishes to give it away, perhaps out of grudge or hope of hitting up the winner later. The staffer has no contact at all with the contestant, who knows nothing except perhaps having read this GLL post, and sees nothing except the final arrangement of the coins. Can the staffer communicate the winning square just by having flipped one coin, and if so, how? That is the puzzle.

Note that the employee has no control over the setup of the coins which is completely random. The configuration after flipping one coin was just as likely as the original to be chosen randomly. So how can six bits of information have been transmitted?

Toward a Solution

I shared this puzzle with Vipul Goyal when he visited Tech last month. He is currently at Microsoft Research in India and does strong research in cryptography, security, and privacy—not surprising since he did his PhD at UCLA under Rafail Ostrovsky and Amit Sahai. It took awhile for him to understand why it could even remotely be soluble, but that evening he sent me a complete solution. Impressive. He has given permission for me to relate it. First, let me re-phrase the puzzle not in Ken’s way or the source’s way with a jailer and two prisoners, but in simple complexity terms:

Alice receives a string {x} of length {n=2^{k}}. She also receives an index {i} in {\{1,\dots,n\}}. She must flip one bit of {x} so that when Bob receives the resulting string {x'} he can always get {i}.

Now here is how Alice can send one bit, namely whether {i} is even or odd. If {i} is odd and {x} has an even number of 1’s in the first half, she flips a bit in the first half, likewise if {i} is even and {x} has an odd number of 1’s in the first half. Otherwise she flips a bit in the second half. Then in {x'} the parity of {i} and the parity of the count of {1}s in the first half always agree. Thus Bob has narrowed down the possibilities by half. In chessboard terms this is like choosing to flip a coin on White’s side or Black’s side of the board.

Now imagine this scheme using the odd versus even positions in {x}—which is like light versus dark squares on the chessboard—or using the right and left halves of the board. Can we combine these schemes to communicate more bits? If you’re aware of Hamming codes, you might realize that if {x} is initially a codeword, any bit flip will be detectable since the code will correct any one error. But what if {x} is not a codeword? It still needs setting the details down precisely.

Goyal’s Solution

Our source has its own solution and there are others, but let’s see Vipul’s: Denote the input string (to Alice) by {x}, where {|x| = n = 2^k}. Let {x[i]} denote the {i}-th bit of {x}.

We will define sets {S_1, \ldots, S_k}. Each set will contain a subset of the {n} bits from {x} (denoted by their positions in {x}). Denote the parity of all the bits in {S_i} by {P_i}. The {k} bit string that Alice will transmit to Bob will be {P_1, P_2, \ldots, P_k}. The primary challenge will be to choose the sets {S_1, \ldots, S_k} in such a way that exactly by flipping one of the bits from {x}, all the parities can be set to any desired value.

Now to describe how to construct these sets. The key observation is the following. Alice would like to flip the parity of a collection of these {k} sets. That means for every such collection, there must exist a unique bit in {x} which is exactly in all the sets from this collection but not in the sets outside this collection. There exist {2^k} such collections. And this is also exactly the number of bits in {x}. Hence, it appears to be possible to have such sets. These sets are constructed as follows. A bit {x[i]} is in set {S[j]} iff the {j}-th bit of {i} is 1.

Denote the original {k}-bit parity string for the sets to be {P_{original}} and the {k} bit string that Alice wants to communicate to Bob to be {P_{final}}. Let {C = P_{original} \oplus P_{final}}. Now the parity of {S_i} must be flipped iff {C[i]} is 1. We will simply flip the bit {x[C]} and observe that {x[C] \in \{S_i\}_{C[i] = 1}} but {x[C] \notin \{S_i\}_{C[i] \neq 1}} (by construction).

Open Problems

Did you know this fact about communication? Are there any possible applications that come to mind?

Incidentally, today is Pi Day 3/14, indeed rounded Pi Day 3/14/16. Georges-Louis Leclerc, Comte de Buffon, famously showed how to approximate {\pi} probabilistically by randomly throwing a needle the width of one tile on a square-tiled floor and counting whether it crosses a vertical side of a square. Suppose we randomly toss a coin on the floor instead. Depending on the width of the coin relative to a tile—assuming it’s a rational number—can we ever get an estimate for {\pi} that way?

7 Comments leave one →
  1. Hajduk permalink
    March 15, 2016 8:30 am

    I vaguely remember that this idea works iff n is a power of two but I can’t give any details.

  2. March 15, 2016 12:00 pm

    It is trivially to see the lower bound of finding the maximum in a set of integers must be in linear time when the set is not previously sorted. In this way, the language MAXIMUM is defined as follows:

    Given a set S of n (distinct) positive integers and an integer x, MAXIMUM is the problem of deciding whether x is the maximum number in S.

    Now, we could define the succinct version of this problem:

    A succinct representation of a set of (distinct) b-bits positive integers is a Boolean circuit C with b input gates. The set represented by C, denoted S_{C}, is defined as follows: Every possible integer of S_{C} should be between 0 and (2^{b} – 1). And j is an element of S_{C} if and only if C accepts the binary representation of the b-bits integer j as input. The problem SUCCINCT MAXIMUM is now this: Given the succinct representation C of a set S_{C} and a b-bits integer x, where C is a Boolean circuit with b input gates, is x the maximum in S_{C}?

    It is very easy to show this problem is not in P, because we should need n comparisons to know whether x is the maximum in a set of n (distinct) positive integers when the set is arbitrary. And this number of comparisons will be optimal. This would mean we cannot always accept every instance (C; x) of SUCCINCT MAXIMUM in polynomial-time, because we must use at least n = |S_{C}| comparisons for infinite amount of cases, where |S_{C}| is the cardinality of S_{C}. However, n could be exponentially more large than the size of (C; x). This does not mean we could not do it for some cases (for example when x = 2^{b} – 1), that’s why we use the phrase “we cannot always accept … in polynomial-time”

    But, at the same time, it is so easy to show this problem is in coNP. Certainly, given a b-bits integer y, we can check whether C accepts the binary representation of y (which means that y is an element of S_{C}) and x < y in polynomial-time, since the comparison of two b-bits integers can be done in polynomial-time and the efficiency of the acceptance of y by C only depends in the size of the circuit. And thus, we could verify whether (C; x) is a "no" instance of SUCCINCT MAXIMUM in polynomial-time.

    However, the existence of a problem in coNP and not in P is sufficient to show that P is not equal to NP, because if P would be equal to NP, then P = coNP.

    Basically is this, but you could see more in

    https://hal.archives-ouvertes.fr/hal-01281254/document

  3. March 16, 2016 1:36 am

    A more general form of the solution, bringing it even closer to error correcting codes, is to cast the 64-bit string as an element in GF(2^6), i.e., compute its remainder modulo some fixed polynomial f(x) from Z_2[x] of degree 6. To see that any number can be communicated this way, it suffices to pick the polynomial so that all x^i mod f(x) are different for i = 0..63, i.e., x is a primitive element in Z_2[x]/f(x).

  4. March 16, 2016 6:31 am

    At large scale, this encoding method would amplify the bandwidth of steganography.

  5. Sam permalink
    March 17, 2016 9:51 am

    I’m pretty sure that the puzzle as stated – “the staffer has no contact at all with the contestant” – is impossible. The staffer and contestant would have to have agreed on a protocol in advance.

    • March 17, 2016 10:00 am

      The contestant has read this post (or some equivalent source). No contact for giving away the square is important.

  6. Ravi permalink
    March 21, 2016 12:36 am

    Philip Hall Strikes Again

    Another neat application of Hall’s marriage theorem. Create a bipartite graph G in which V1 = V2 = the set of strings of length 64. An edge between u in V1 to v in V2 is added if and only of the Hamming distance between u and v is exactly 1 (i.e., u and v differ in exactly 1 bit). G is a regular bipartite graph (with each vertex degree = 64) and by Hall’s theorem, G has a perfect matching. The two prisoners memorize this perfect matching, and the first prisoner when shown vertex u in V1 (by the guard), looks at the unique vertex v it is connected to in V2 in the perfect matching, and flips the bit that changes u to v. The second prisoner sees v and applies the inverse of the bijective mapping (associated with the perfect matching) to determine which bit got flipped.

    Numerous variations of secret communication through a perfect matching in bipartite graph exists – the most famous being Cheney’s puzzle, apparently created by Cheney, a magician who was the first PhD graduate of MIT.(For more details, see Kleber’s paper in Math Intelligencer: http://www.apprendre-en-ligne.net/crypto/magie/card.pdf)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s