Before revision:  We conjecture that our oracle complexity is tight up to constant factors for polynomial time algorithms. Our result immediately implies a strongly polynomial algorithm for the Submodular Function Minimization problem that makes at most O(n^3) calls to an evaluation oracle .
After revision:  For the Submodular Function Minimization problem, our result immediately implies a strongly polynomial algorithm for the Submodular Function Minimization problem that makes at most O(n^3) calls to an evaluation oracle .