Young Uri Tachman - Solution

Russ did not like the time saving mechanism. He noticed that Uri can cheat by switching the envelopes between the left and the right experiments conducted in parallel (i.e. giving the experimenter in the left experiment the envelope Uri received from him in the right experiment and vice versa). Therefore if the experementer chooses bits b and c Uri will succeed if b is different from c, which happens with probability 1/2 (rather than 1/4 if the two experiments were truly independent).

To read more about the the problems of executing protocols in parallel see a paper ( Abstract, Postscript , gzipped Postscript ) by Mihir Bellare , Russ Impagliazzo and Moni Naor.


Back to the Puzzler page