Sharp Power Loss Thresholds for Vector Min UncutResearch Paper
Vector Min Uncut asks for unit vectors, one per vertex of a weighted graph, such that the endpoints of every heavy edge are nearly antipodal. At rank one the vectors are signs and the problem is classical Min Uncut, the complement of Max-Cut, for which Agarwal, Charikar, Makarychev and Makarychev gave an -approximation (STOC 2005).…