Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow

All-Pairs Minimum Cut (APMC) is a fundamental graph problem that asks to find a minimum s,t-cut for every pair of vertices s,t. A recent line of work on fast algorithms for APMC has culminated with a reduction of APMC to polylog(n)-many max-flow computations. But unfortunately, no fast algorithms are currently known for exact max-flow in several standard models of computation, such as the cut-query model and the fully-dynamic model.