Max-k-Cut and correlation clustering are fundamental graph partitioning problems. The methods with the best approximation guarantees for Max-k-Cut and the Max-Agree variant of correlation clustering involve solving SDPs with n^2 variables and n^2 constraints (where n is the number of vertices). Large-scale instances of SDPs, thus, present a memory bottleneck. In this paper, we develop a simple polynomial-time Gaussian sampling-based algorithms for these two problems that use 𝒪(n+|E|) memory and…