Conference paper
On the hardness of approximating multicut and sparsest-cut
Shuchi Chawla, Robert Krauthgamer, et al.
CCC 2005
Paper
Information theory methods in communication complexity
Related
Conference paper
On the memory requirements of XPath evaluation over XML streams
Ziv Bar-Yossef, Marcus Fontoura, et al.
SIGMOD/PODS/ 2004
Conference paper
Lower bounds for randomized read/write stream algorithms
Paul Beame, T.S. Jayram, et al.
STOC 2007
Moses Charikar, Jon Kleinberg, et al.
SIAM Journal on Discrete Mathematics