  Max-k-Cut and correlation clustering are fundamental graph partitioning
problems. For a graph with G=(V,E) with n vertices, the methods with the best
approximation guarantees for Max-k-Cut and the Max-Agree variant of correlation
clustering involve solving SDPs with $O(n^2)$ variables and constraints.
Large-scale instances of SDPs, thus, present a memory bottleneck. In this
paper, we develop simple polynomial-time Gaussian sampling-based algorithms for
these two problems that use $O(n+|E|)$ memory and nearly achieve the best
existing approximation guarantees. For dense graphs arriving in a stream, we
eliminate the dependence on $|E|$ in the storage complexity at the cost of a
slightly worse approximation ratio by combining our approach with
sparsification.
