  We consider the classical Minimum Balanced Cut problem: given a graph $G$,
compute a partition of its vertices into two subsets of roughly equal volume,
while minimizing the number of edges connecting the subsets. We present the
first {\em deterministic, almost-linear time} approximation algorithm for this
problem. Specifically, our algorithm, given an $n$-vertex $m$-edge graph $G$
and any parameter $1\leq r\leq O(\log n)$, computes a $(\log
m)^{r^2}$-approximation for Minimum Balanced Cut on $G$, in time $O\left (
m^{1+O(1/r)+o(1)}\cdot (\log m)^{O(r^2)}\right )$. In particular, we obtain a
$(\log m)^{1/\epsilon}$-approximation in time $m^{1+O(1/\sqrt{\epsilon})}$ for
any constant $\epsilon$, and a $(\log m)^{f(m)}$-approximation in time
$m^{1+o(1)}$, for any slowly growing function $m$. We obtain deterministic
algorithms with similar guarantees for the Sparsest Cut and the
Lowest-Conductance Cut problems.
  Our algorithm for the Minimum Balanced Cut problem in fact provides a
stronger guarantee: it either returns a balanced cut whose value is close to a
given target value, or it certifies that such a cut does not exist by
exhibiting a large subgraph of $G$ that has high conductance. We use this
algorithm to obtain deterministic algorithms for dynamic connectivity and
minimum spanning forest, whose worst-case update time on an $n$-vertex graph is
$n^{o(1)}$, thus resolving a major open problem in the area of dynamic graph
algorithms. Our work also implies deterministic algorithms for a host of
additional problems, whose time complexities match, up to subpolynomial in $n$
factors, those of known randomized algorithms. The implications include
almost-linear time deterministic algorithms for solving Laplacian systems and
for approximating maximum flows in undirected graphs.
