  A $k$-vertex connectivity oracle for undirected $G$ is a data structure that,
given $u,v\in V(G)$, reports $\min\{k,\kappa(u,v)\}$, where $\kappa(u,v)$ is
the pairwise vertex connectivity between $u,v$. There are three main measures
of efficiency: construction time, query time, and space. Prior work of Izsak
and Nutov shows that a data structure of total size $\tilde{O}(kn)$ can even be
encoded as a $\tilde{O}(k)$-bit labeling scheme so that vertex-connectivity
queries can be answered in $\tilde{O}(k)$ time. The construction time is
polynomial, but unspecified.
  In this paper we address the top three complexity measures: Space, Query
Time, and Construction Time. We give an $\Omega(kn)$-bit lower bound on any
vertex connectivity oracle. We construct an optimal-space connectivity oracle
in max-flow time that answers queries in $O(\log n)$ time, independent of $k$.
