While many theoretical approximation algorithms exist for graph partitioning, they often rely on multicommodity-flow computations that are quadratic time in the worst case and are too time-consuming for the massive graphs that are prevalent in today's applications. In this thesis, we study the design of approximation algorithms that yield strong approximation ratios, while running in subquadratic time and relying on computational procedures that are often fast in practice.
Our algorithms employ spectral and s-t flow operations to explore the cuts of a graph in a very efficient way. A crucial ingredient in their design is the usage of random walks that capture the sparse cuts of a graph better than single eigenvectors. The analysis of our methods is particularly simple, as it relies on a semidefinite programming formulation of the graph partitioning problem of choice. Indeed, we can develop our algorithms as primal-dual methods for solving a semidefinite program and show that certain random walks arise naturally from this approach.