  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 solutions to this problem are based on error-correcting
coding techniques and suffer from a large decoding time. Existing probabilistic
solutions based on Invertible Bloom Lookup Tables (IBLTs) are time-efficient
but offer insufficient success guarantees for many applications. Here we
propose a tunable trade-off between the two approaches combining the efficiency
of IBLTs with exponentially decreasing failure probability. The proof relies on
a refined analysis of IBLTs proposed in (Baek Tejs Houen et al. SOSA 2023)
which has an independent interest. We also propose a modification of our
algorithm that enables telling apart the elements of each set in the symmetric
difference.
