. We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most _ϕ_, whose small side has volume at least 2b, in time _O_(2b log2_m/ϕ_2) where _m_ is the number of edges in the graph. By combining small sets found by this local partitioning algorithm, we obtain a cut with conductance _ϕ_ and approximately optimal balance in time _O_(_m_ log4_m/ϕ_2).">