Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries

We give the first deterministic algorithm that makes sub-quadratic queries to find the global min-cut of a simple graph in the cut query model. Given an n-vertex graph G, our algorithm makes widetildeO(n5/3) queries to compute the global min-cut in G. As a key ingredient, we also show an algorithm for finding s-t max-flows of size widetildeO(n) in widetildeO(n5/3) queries. We also show efficient cut-query implementations of versions of expander decomposition and isolating cuts, which may be of independent interest.