Conference paper
A note on the set systems used for broadcast encryption
Ravi Kumar, Alexander Russell
SODA 1998
Paper
On the hardness of approximating multicut and sparsest-cut
Abstract
We show that the Multicut, Sparsest-Cut, and Min-2CNF≡. Deletion problems are NP-hard to approximate within every constant factor, assuming the Unique Games Conjecture of Khot (2002). A quantitatively stronger version of the conjecture implies an inapproximability factor of Ω(√log log n). © Birkhäuser Verlag, Basel 2006.
Related
Tuǧkan Batu, Sanjoy Dasgupta, et al.
Proceedings of the Annual IEEE Conference on Computational Complexity
Conference paper
Rank aggregation methods for the web
Cynthia Dwork, Ravi Kumar, et al.
WWW 2001
Conference paper
Algorithms on negatively curved spaces
Robert Krauthgamer, Jmes R. Lee
FOCS 2006