Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Locality-Preserving Hashing for Shifts with Connections to Cryptography
event speaker icon
Ohad Klein (Bar-Ilan University)
event date icon
Wednesday, 30.03.2022, 12:30
event location icon
Taub 201 Taub Bld.
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.