  In the simultaneous Max-Cut problem, we are given $k$ weighted graphs on the
same set of $n$ vertices, and the goal is to find a cut of the vertex set so
that the minimum, over the $k$ graphs, of the cut value is as large as
possible. Previous work [BKS15] gave a polynomial time algorithm which achieved
an approximation factor of $1/2 - o(1)$ for this problem (and an approximation
factor of $1/2 + \epsilon_k$ in the unweighted case, where $\epsilon_k
\rightarrow 0$ as $k \rightarrow \infty$).
  In this work, we give a polynomial time approximation algorithm for
simultaneous Max-Cut with an approximation factor of $0.8780$ (for all constant
$k$). The natural SDP formulation for simultaneous Max-Cut was shown to have an
integrality gap of $1/2+\epsilon_k$ in [BKS15]. In achieving the better
approximation guarantee, we use a stronger Sum-of-Squares hierarchy SDP
relaxation and a rounding algorithm based on Raghavendra-Tan [RT12], in
addition to techniques from [BKS15].
