Conference paper
A note on the set systems used for broadcast encryption
Ravi Kumar, Alexander Russell
SODA 1998
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.
Ravi Kumar, Alexander Russell
SODA 1998
Tuǧkan Batu, Sanjoy Dasgupta, et al.
Proceedings of the Annual IEEE Conference on Computational Complexity
Cynthia Dwork, Ravi Kumar, et al.
WWW 2001
Robert Krauthgamer, Jmes R. Lee
FOCS 2006