All-Pairs Minimum Cut using Õ(n7/4) Cut Queries

We present the first non-trivial algorithm for the all-pairs minimum cut problem in the cut-query model. Given cut-query access to an unweighted graph $G = (V,E)$ with $n$ vertices, our randomized algorithm constructs a Gomory-Hu tree of $G$, and thus solves the all-pairs minimum cut problem, using $\tilde O(n^{7/4})$ cut queries.