  Vertex connectivity a classic extensively-studied problem. Given an integer
$k$, its goal is to decide if an $n$-node $m$-edge graph can be disconnected by
removing $k$ vertices. Although a linear-time algorithm was postulated since
1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge
connectivity being resolved over two decades ago [Karger STOC'96], so far no
vertex connectivity algorithms are faster than $O(n^2)$ time even for $k=4$ and
$m=O(n)$. In the simplest case where $m=O(n)$ and $k=O(1)$, the $O(n^2)$ bound
dates five decades back to [Kleitman IEEE Trans. Circuit Theory'69]. For
general $k$ and $m$, the best bound is $\tilde{O}(\min(kn^2,
n^\omega+nk^\omega))$.
  In this paper, we present a randomized Monte Carlo algorithm with
$\tilde{O}(m+k^{7/3}n^{4/3})$ time for any $k=O(\sqrt{n})$. This gives the {\em
first subquadratic time} bound for any $4\leq k \leq o(n^{2/7})$ and improves
all above classic bounds for all $k\le n^{0.44}$. We also present a new
randomized Monte Carlo $(1+\epsilon)$-approximation algorithm that is strictly
faster than the previous Henzinger's 2-approximation algorithm [J.
Algorithms'97] and all previous exact algorithms.
  The key to our results is to avoid computing single-source connectivity,
which was needed by all previous exact algorithms and is not known to admit
$o(n^2)$ time. Instead, we design the first local algorithm for computing
vertex connectivity; without reading the whole graph, our algorithm can find a
separator of size at most $k$ or certify that there is no separator of size at
most $k$ `near' a given seed node.
