Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.

Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev

Browse the full SODA paper archive.