In a secure multi-party computation problem, players are required to compute a function of their private inputs without revealing any extra information about this input to other players.

A Simple Stochastic Game is a game with a reachability objective played by two players on a directed graph. Each vertex of the graph is either controlled by one of the players or is a probabilistic vertex.

Can a sender encode a pair of messages (m0, m1) jointly, and send their encoding over (say) a binary erasure channel, so that the receiver can decode exactly one of the two messages and the sender does not know which one?

We know that for matrices A and B, AB is not the same as BA in general. But suppose B is a polynomial in A, like B = A^2 - 3A + I (note I = A^0). Then AB is indeed the same as BA.

A p-random restriction is a random partial input obtained by independently leaving each input variable unset with probability p setting them to either 0,1 with (1-p)/2 each.