Constant Factor Approximation for Balanced Cut in the PIE model

We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V partitioned into two clusters L and R of equal size. Let G be an arbitrary graph on V with no edges between L and R. Let Erandom be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under permutation of vertices in L and in R). Then we say that G + Erandom is a graph with permutation-invariant random edges. We present an approximation algorithm for the Balanced Cut problem that finds a balanced cut of cost O(|Erandom|) + n polylog(n) in this model. In the regime when |Erandom| = Omega(n polylog(n)), this is a constant factor approximation with respect to the cost of the planted cut.