  In this work, we resolve the query complexity of global minimum cut problem
for a graph by designing a randomized algorithm for approximating the size of
minimum cut in a graph, where the graph can be accessed through local queries
like {\sc Degree}, {\sc Neighbor}, and {\sc Adjacency} queries.
  Given $\epsilon \in (0,1)$, the algorithm with high probability outputs an
estimate $\hat{t}$ satisfying the following $(1-\epsilon) t \leq \hat{t} \leq
(1+\epsilon) t$, where $m$ is the number of edges in the graph and $t$ is the
size of minimum cut in the graph. The expected number of local queries used by
our algorithm is $\min\left\{m+n,\frac{m}{t}\right\}\mbox{poly}\left(\log
n,\frac{1}{\epsilon}\right)$ where $n$ is the number of vertices in the graph.
Eden and Rosenbaum showed that $\Omega(m/t)$ many local queries are required
for approximating the size of minimum cut in graphs. These two results together
resolve the query complexity of the problem of estimating the size of minimum
cut in graphs using local queries.
  Building on the lower bound of Eden and Rosenbaum, we show that, for all $t
\in \mathbb{N}$, $\Omega(m)$ local queries are required to decide if the size
of the minimum cut in the graph is $t$ or $t-2$. Also, we show that, for any $t
\in \mathbb{N}$, $\Omega(m)$ local queries are required to find all the minimum
cut edges even if it is promised that the input graph has a minimum cut of size
$t$. Both of our lower bound results are randomized, and hold even if we can
make {\sc Random Edge} query apart from local queries.
