Date Added: Apr 2012
The authors study error estimating codes with the goal of establishing better bounds for the theoretical and empirical overhead of such schemes. They explore the idea of using sketch data structures for this problem, and show that the tug-of-war sketch gives an asymptotically optimal solution. The optimality of their algorithms are proved using communication complexity lower bound techniques. They, then propose a novel enhancement of the tug-of-war sketch that greatly reduces the communication overhead for realistic error rates. Their theoretical analysis and assertions are supported by extensive experimental evaluation.