link

May 31, Tuesday
12:00 – 13:00

Reconciliation of Distributed Data
Computer Science seminar
Lecturer : Ari Trachtenberg
Lecturer homepage : http://people.bu.edu/trachten/
Affiliation : Electrical and Computer Engineering Department, Boston University
Location : 202/37
Host : Dr. Aryeh Kontorovich
The ability to share and reconcile similar data on remote hosts with minimum communication is fundamental and inherent to a wide variety of networking applications, ranging from maintenance of your contacts across smartphones to synchronizing video fragments from moon rovers. In this talk we provide a selective survey of ten years of our research on this problem, together with applications to the information theory and cryptography communities.

We will begin with a concrete formalization of the problem of reconciling sets, and our initial solution based on polynomial interpolation. We will then present and analyze information-theoretic bounds, estimation techniques, and interactive solutions to this problem, together with an extension to string reconciliation. Throughout, we will describe applications tied to this problem and developed by others, such as the current standard for synchronizing PGP key databases and secure sketches for biometric authentication.