The Taub Faculty of Computer Science Events and Talks

Alice receives a non-periodic string (such as ABCDEF), while Bob receives a string (such as CDEFAB), obtained by applying a hidden cyclic shift to Alice’s string. Alice and Bob query their strings in a small number of positions (sublinear in the amount of shifting) and then exchange a single short message. How can they detect the shift with minimal error probability? Based on Joint works with Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller.