Before revision:  Moreover, for every integer 1 }\le \le \tau) many queries to the adjacency matrix of G. These results contrast with the classical randomized case where } \Omega(n^2) and \Omega(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases.
After revision:  Moreover, for every integer 1 }\le \le n we give an example of a graph G with edge weights 1 and \tau such that solving the minimum cut problem on G requires \Omega(n^{3/2\tau) many queries to the adjacency matrix of G. These results contrast with the classical randomized case where } \Omega(n^2) and \Omega(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases.