  Consider the following "local" cut-detection problem in a directed graph: We
are given a starting vertex $s$ and need to detect whether there is a cut with
at most $k$ edges crossing the cut such that the side of the cut containing $s$
has at most $\Delta$ interior edges. If we are given query access to the input
graph, then this problem can in principle be solved in sublinear time without
reading the whole graph and with query complexity depending on $k$ and
$\Delta$. We design an elegant randomized procedure that solves a slack variant
of this problem with $O(k^2 \Delta)$ queries, improving in particular a
previous bound of $O((2(k+1))^{k+2} \Delta)$ by Chechik et al. [SODA 2017]. In
this slack variant, the procedure must successfully detect a component
containing $s$ with at most $k$ outgoing edges and $\Delta$ interior edges if
such a component exists, but the component it actually detects may have up to
$O(k \Delta)$ interior edges.
  Besides being of interest on its own, such cut-detection procedures have been
used in many algorithmic applications for higher-connectivity problems. Our new
cut-detection procedure therefore almost readily implies (1) a faster vertex
connectivity algorithm which in particular has nearly linear running time for
polylogarithmic value of the vertex connectivity, (2) a faster algorithm for
computing the maximal $k$-edge connected subgraphs, and (3) faster property
testing algorithms for higher edge and vertex connectivity, which resolves two
open problems, one by Goldreich and Ron [STOC '97] and one by Orenstein and Ron
[TCS 2011].
