Max cut for random graphs with a planted partition

We give an algorithm that, with high probability, recovers a planted k-partition in a random graph, where edges within vertex classes occur with probability p and edges between vertex classes occur with probability r greater than or equal to p + croot(plogn/n). The algorithm can handle vertex classes of different sizes and, for fixed k, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.