  An $n$-vertex $m$-edge graph is \emph{$k$-vertex connected} if it cannot be
disconnected by deleting less than $k$ vertices. After more than half a century
of intensive research, the result by [Li et al. STOC'21] finally gave a
\emph{randomized} algorithm for checking $k$-connectivity in near-optimal
$\widehat{O}(m)$ time. (We use $\widehat{O}(\cdot)$ to hide an $n^{o(1)}$
factor.) Deterministic algorithms, unfortunately, have remained much slower
even if we assume a linear-time max-flow algorithm: they either require at
least $\Omega(mn)$ time [Even'75; Henzinger Rao and Gabow, FOCS'96; Gabow,
FOCS'00] or assume that $k=o(\sqrt{\log n})$ [Saranurak and
Yingchareonthawornchai, FOCS'22]. We show a \emph{deterministic} algorithm for
checking $k$-vertex connectivity in time proportional to making
$\widehat{O}(k^{2})$ max-flow calls, and, hence, in $\widehat{O}(mk^{2})$ time
using the deterministic max-flow algorithm by [Brand et al. FOCS'23]. Our
algorithm gives the first almost-linear-time bound for all $k$ where
$\sqrt{\log n}\le k\le n^{o(1)}$ and subsumes up to a sub polynomial factor the
long-standing state-of-the-art algorithm by [Even'75] which requires
$O(n+k^{2})$ max-flow calls. Our key technique is a deterministic algorithm for
terminal reduction for vertex connectivity: given a terminal set separated by a
vertex mincut, output either a vertex mincut or a smaller terminal set that
remains separated by a vertex mincut. We also show a deterministic
$(1+\epsilon)$-approximation algorithm for vertex connectivity that makes
$O(n/\epsilon^2)$ max-flow calls, improving the bound of $O(n^{1.5})$ max-flow
calls in the exact algorithm of [Gabow, FOCS'00]. The technique is based on
Ramanujan graphs.
