We give the first combinatorial approximation algorithm for Maxcut that beats the trivial 0.5 factor by a constant. The main partitioning procedure is very intuitive, natural, and easily described. It essentially performs a number of random walks and aggregates the information to provide the partition. We can control the running time to get an approximation factor-running time tradeoff. We show that for any constant $$b > 1.5$$, there is an $$O(n^b)$$ algorithm that outputs a $$(0.5+\delta)$$ approximation for Maxcut, where $$\delta = \delta(b)$$ is some positive constant.
One of the components of our algorithm is a weak local graph partitioning procedure that may be of independent interest. Given a starting vertex $$i$$ and a conductance parameter $$\phi$$, unless a random walk of length $$l = O(\log n)$$ starting from $$i$$ mixes rapidly (in terms of $$\phi$$ and $$l$$), we can find a cut of conductance at most $$\phi$$ close to the vertex. The work done per vertex found in the cut is sublinear in $$n$$.