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. In contrast, we show upper bounds of \tilde O(n^{3/2\tilde  ) and \tilde O( \sqrt{mn + n^{3/2}), respectively, where again the edge weights are between 1 and \tau.
After 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) queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when G has m edges the classical randomized complexity of the minimum cut problem is \tilde O(n^{3/2\tilde ) and \tilde O( \sqrt{mn + n^{3/2}), respectively, where again the edge weights are between 1 and \tau.