Ohad Klein (Bar-Ilan University)
Wednesday, 30.3.2022, 12:30
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.