Conference paper
On sketching quadratic forms
Alexandr Andoni, Jiecao Chen, et al.
ITCS 2016
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
Conference paper
Min-max graph partitioning and small set expansion
Nikhil Bansal, Uriel Feige, et al.
FOCS 2011
Ronald Fagin, Ravi Kumar, et al.
SIGMOD 2003
Conference paper
Propagation of trust and distrust
R. Guha, Prabhakar Raghavan, et al.
WWW 2004