  We improve upon the running time for finding a point in a convex set given a
separation oracle. In particular, given a separation oracle for a convex set
$K\subset \mathbb{R}^n$ contained in a box of radius $R$, we show how to either
find a point in $K$ or prove that $K$ does not contain a ball of radius
$\epsilon$ using an expected $O(n\log(nR/\epsilon))$ oracle evaluations and
additional time $O(n^3\log^{O(1)}(nR/\epsilon))$. This matches the oracle
complexity and improves upon the $O(n^{\omega+1}\log(nR/\epsilon))$ additional
time of the previous fastest algorithm achieved over 25 years ago by Vaidya for
the current matrix multiplication constant $\omega<2.373$ when
$R/\epsilon=n^{O(1)}$.
  Using a mix of standard reductions and new techniques, our algorithm yields
improved runtimes for solving classic problems in continuous and combinatorial
optimization:
  Submodular Minimization: Our weakly and strongly polynomial time algorithms
have runtimes of $O(n^2\log nM\cdot\text{EO}+n^3\log^{O(1)}nM)$ and
$O(n^3\log^2 n\cdot\text{EO}+n^4\log^{O(1)}n)$, improving upon the previous
best of $O((n^4\text{EO}+n^5)\log M)$ and $O(n^5\text{EO}+n^6)$.
  Matroid Intersection: Our runtimes are $O(nrT_{\text{rank}}\log n\log (nM)
+n^3\log^{O(1)}(nM))$ and $O(n^2\log (nM) T_{\text{ind}}+n^3 \log^{O(1)}
(nM))$, achieving the first quadratic bound on the query complexity for the
independence and rank oracles. In the unweighted case, this is the first
improvement since 1986 for independence oracle.
  Submodular Flow: Our runtime is $O(n^2\log
nCU\cdot\text{EO}+n^3\log^{O(1)}nCU)$, improving upon the previous bests from
15 years ago roughly by a factor of $O(n^4)$.
  Semidefinite Programming: Our runtime is $\tilde{O}(n(n^2+m^{\omega}+S))$,
improving upon the previous best of $\tilde{O}(n(n^{\omega}+m^{\omega}+S))$ for
the regime where the number of nonzeros $S$ is small.
