  We give query-efficient algorithms for the global min-cut and the s-t cut
problem in unweighted, undirected graphs. Our oracle model is inspired by the
submodular function minimization problem: on query $S \subset V$, the oracle
returns the size of the cut between $S$ and $V \setminus S$.
  We provide algorithms computing an exact minimum $s$-$t$ cut in $G$ with
$\tilde{O}(n^{5/3})$ queries, and computing an exact global minimum cut of $G$
with only $\tilde{O}(n)$ queries (while learning the graph requires
$\tilde{\Theta}(n^2)$ queries).
