  We study faster algorithms for producing the minimum degree ordering used to
speed up Gaussian elimination. This ordering is based on viewing the non-zero
elements of a symmetric positive definite matrix as edges of an undirected
graph, and aims at reducing the additional non-zeros (fill) in the matrix by
repeatedly removing the vertex of minimum degree. It is one of the most widely
used primitives for pre-processing sparse matrices in scientific computing.
  Our result is in part motivated by the observation that sub-quadratic time
algorithms for finding min-degree orderings are unlikely, assuming the strong
exponential time hypothesis (SETH). This provides justification for the lack of
provably efficient algorithms for generating such orderings, and leads us to
study speedups via degree-restricted algorithms as well as approximations. Our
two main results are: (1) an algorithm that produces a min-degree ordering
whose maximum degree is bounded by $\Delta$ in $O(m \Delta \log^3{n})$ time,
and (2) an algorithm that finds an $(1 + \epsilon)$-approximate marginal
min-degree ordering in $O(m \log^{5}n \epsilon^{-2})$ time.
  Both of our algorithms rely on a host of randomization tools related to the
$\ell_0$-estimator by [Cohen `97]. A key technical issue for the final
nearly-linear time algorithm are the dependencies of the vertex removed on the
randomness in the data structures. To address this, we provide a method for
generating a pseudo-deterministic access sequence, which then allows the
incorporation of data structures that only work under the oblivious adversary
model.
