  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 ell = O(log n)
starting from i mixes rapidly (in terms of phi and ell), 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.
