Subscribe to Events

____________________________________________

IN-PERSON MATHEMATICAL PHYSICS SEMINAR
RUTGERS UNIVERSITY
HILL 705
____________________________________________

COFFEE WILL BE AVAILABLE AT 11:50. THERE WILL BE A BROWN BAG LUNCH AFTER THE SEMINAR.

IF YOU HAVE ANY QUESTIONS PLEASE EMAIL ME AT 

Michael Saks – Rutgers University

Date/Time/Location
Thursday, October 19th, 12:00pm; Hill Center 705

Synchronization via small sketches  

Consider the situation of two separated computers A and B where computer A stores a large file F of n bits (where n is, say, one trillion ) and B stores a file G. G is supposed to be a copy of F, but over time the files became unsynchronized. We wish to restore synchronization. The obvious thing to do is for A to transmit F to B, so that B can replace G by F. This requires an amount of communication equal to the size n of F. Is there a way to do this with less communication?

If we make no assumptions about the relationship between G and F then, for information theoretic reasons, there’s no way to reduce the amount of communication. However, it is reasonable to assume that G is, in some sense, “close” to F. Can this assumption be used to reduce the communication?

To formalize this problem we measure closeness of G to F by the edit distance metric. Here d(G,F) is defined to be the minimum number of elementary changes to transform G to F where an elementary change is to delete a character, insert a character, or replace one character with another.