Linear Set Reconciliation with Additive Redundancy
En palabras de los autores
In set reconciliation, two parties holding sets with seek to recover their symmetric difference from short -linear sketches, which is equivalent to recovering a -sparse vector from its syndrome . While the information-theoretic counting bound requires bits, existing polynomial-time schemes either use at least bits (algebraic sketches, leaving an -bit gap) or incur a multiplicative overhead (peeling-based sketches), raising the question of whether bits is achievable with fast updates and decoding. We construct a public-coin randomized -linear sketch of length that recovers each fixed input of weight at most with probability at least , with update time and worst-case decoding time. In particular, for and , this achieves bits with update time and decoding time. Our construction encodes permuted rows via randomly scaled Pinsketch syndromes and sketches the resulting bit array column by column. Decoding columns sequentially from prefix predictions cancels recovered rows and exposes undecided rows as decoder-side hints, reducing each column to a hinted sparse recovery problem that we solve via a recursive sketch, HintSketch.
Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.