A computability perspective on William Slofstra’s resolution of the strong Tsirelson problem

In William Slofstra’s breakthrough paper, he proves a general group embedding theorem relating to binary constraint games. (This is a wonderful proof which I’ll post some exposition about soon.) From this, he derives two very nice corollaries regarding what kinds of correlations are possible with different axioms quantum mechanics. In this note, we’ll show that one of these corollaries (or a weakened form thereof) can be derived from the other in a potentially interesting way. This leads to a question for which I’m very surprised not to know the answer: is there an algorithm to compute the approximate value of a nonlocal game, even given access to an oracle solving the halting problem?

Continue reading “A computability perspective on William Slofstra’s resolution of the strong Tsirelson problem”

A countable cup game and certifiable randomness

Consider the following game:

There is a countable sequence of face-down cups and an infinite bag of balls. First, player one places balls underneath finitely many of the cups. Next, player two turns over some (possibly infinite) set of cups and looks to see if they have balls underneath them. Finally, player two points to a cup that she has not yet turned over and declares “this cup does not have a ball underneath it.” Player two wins if her guess is correct; otherwise player one wins.

What’s a good strategy for player two in this game?

Continue reading “A countable cup game and certifiable randomness”

A Countable Hat Game and the Kolmogorov 0-1 Law

Last term, I took a lovely class in probability theory with Professor Omer Tamuz. On the first problem set, he posed an interesting bonus problem about a certain game played by a countable sequence of players wearing colored hats. The game goes like this:

Countably many cooperating players (P_1, P_2, P_3,\ldots) stand in a line indexed by \mathbb N. A neutral game master walks down the row of players, placing black and white hats on the player’s heads independently and uniformly at random. (In other words, the color of each player’s hat is decided by a fresh fair coin flip.) Afterwards, the game master goes through again, asking each player in turn to announce a guess for their own hat color. Each player hears the guesses of the players that came before them and sees all of the hats on the heads of people ahead of them. The players win if everyone except for the first person guesses correctly. (The first person, of course, is doomed to only guess their hat correctly 50% of the time, regardless of their strategy. However, the rest of the players have a chance to come out ahead by using the information provided by those behind them.)

The players conspire beforehand to come up with a strategy. Is it possible for them to cook up a strategy for which they always win? A bit more conservatively, how about one that wins with probability 1?

Continue reading “A Countable Hat Game and the Kolmogorov 0-1 Law”