Better space-time-robustness trade-offs for set reconciliation

Djamal Belazzougui, Gregory Kucherov, Stefan Walzer

We consider the problem of reconstructing the symmetric difference between similar sets from their representations (sketches) of size linear in the number of differences. Exact sol…