  We present a deterministic (global) mincut algorithm for weighted, undirected
graphs that runs in $m^{1+o(1)}$ time, answering an open question of Karger
from the 1990s. To obtain our result, we de-randomize the construction of the
\emph{skeleton} graph in Karger's near-linear time mincut algorithm, which is
its only randomized component. In particular, we partially de-randomize the
well-known Benczur-Karger graph sparsification technique by random sampling,
which we accomplish by the method of pessimistic estimators. Our main technical
component is designing an efficient pessimistic estimator to capture the cuts
of a graph, which involves harnessing the expander decomposition framework
introduced in recent work by Goranci et al. (SODA 2021). As a side-effect, we
obtain a structural representation of all approximate mincuts in a graph, which
may have future applications.
