[Math] Examples of algorithms requiring deep mathematics to prove correctness

Question

I am looking for examples of algorithms for which the proof of correctness requires deep mathematics ( far beyond what is covered in a normal computer science course).

I hope this is not too broad.

Answer 1

• Group Isomorphism of simple groups. There is a trivial polynomial time algorithm for testing if two (finite) simple groups $G$ and $H$, specified by their multiplication tables, are isomorphic: guess at most two generators $g_1, g_2$ from $G$, then guess two elements of $H$ that they map into, and check if the map extends to an isomorphism. To prove this algorithms is correct, you need to know that every finite simple group can be generated by at most two elements. This follows from the classification theorem, and, as far as I understand, there is little hope of a proof of this fact that does not involve (most of) the classification.

• Testing if a matrix is totally unimodular. A matrix $M \in \{-1, 0, 1\}^{m\times n}$ is totally unimodular (TUM) if the determinant of every one of its submatrices is in the set $\{-1,0,1\}$. The definition gives an exponential number of conditions to verify, so the fact that there is a polynomial time algorithm to test if a given $M$ is TUM is far from obvious. Such an algorithm follows from a deep theorem of Paul Seymour characterizing regular matroids (together with other non-trivial ingredients: the algorithm is given in Schrijver's linear programming book).

• Computing the volume of a convex body. There is a long line of work on algorithms that approximate the volume of a convex body $K$ specified by a membership oracle. The algorithms are based on sampling from $K$ and from modifications of $K$. The sampling itself is done by Markov chain algorithms, which are analyzed using isoperemitric properties of log-concave measures. For example, Kannan, Lovasz and Simonovits (motivated by work on volume computation) proved a lower bound on the Cheeger constant of an isotropic log-concave measure, and conjectured a tighter lower bound. This conjecture, the KLS conjecture, is now a notorious question in asymptotic convex geometry, and implies a number of other deep conjectures: the hyperplane conjecture, and the thin shell conjecture, which themselves have many implications.