Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems

Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou

Partitioning the vertices of a graph into two roughly equal parts while minimizing the number of edges crossing the cut is a fundamental problem (called Balanced Separator) that ar…