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.
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityI 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.
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.
The Miller-Rabin tests determines whether an integer $n$ is prime in time $O_{\epsilon}((\log n)^{4+\epsilon})$. The bound on the running time is conditional on the truth of the Generalized Riemann Hypothesis.
Important comment: The AKS primality test is unconditional and runs in polynomial time (namely $O((\log n)^6)$). Nonetheless Miller-Rabin is in practice much faster and more widely used. Also see comments.
Expanding on one of the comments. Let $E/\mathbb Q$ be an elliptic curve of conductor $N$. (1) There is a finite covering map $f:X_1(N)\to E$ (Wiles' theorem). (2) Let $P\in X_1(N)(\mathbb Q)$ be a Heegner point and let $$Q=\sum_{\sigma\in\text{Gal}(\overline{\mathbb Q}/\mathbb Q)} \sigma(f(P)) \in E(\mathbb Q)$$ be the associated Heegner point on $E$. If $Q$ is not a torsion point, then $\text{rank } E(\mathbb Q)=1$ (Gross-Zagier, Kolyvagin), and thus there is a terminating algorithm to find a generator (since it's relatively easy to find the smallest $Q'\in E(\mathbb Q)$ such that $mQ'=Q+T$ for some rational torsion point $T$). Thus verifying that this algorithm to find a generator of a rank 1 elliptic curve works uses Wiles' modularity theorem to ensure that the covering exists, the Gross-Zagier formula to relate the canonical height of $Q$ to the non-vanishing of $L'(E,1)$, and Kolyvagin's theorem to ensure that the rank is 1.
Many property testing algorithms in the dense graph model rely on the Szemerédi regularity lemma [Sze78], which (essentially) guarantees that every large enough graph can be divided into parts of roughly equal size so that the edges between different parts behave almost as in a random graph.
Using this result, one can obtain algorithms to test many properties of graphs (such as triangle-freeness) with query complexity independent of the size $n$ of the graph. (Although with a pretty insane dependence on the distance parameter $\epsilon$.)
For an exposition of the triangle-freeness testing algorithm and the use of the above result in the analysis, see e.g. Section 13.4 (p.102) of these lecture notes by Rocco Servedio ("Sublinear Time Algorithms in Learning and Property Testing"). Interestingly, the algorithm itself is very simple — 6 lines (Algorithm 12). The analysis, however, takes several pages and crucially relies on the Szemerédi regularity lemma.
[Sze78] E. Szemerédi. Regular partitions of graphs. Problèmes combinatoires et théorie des graphes, pages 399–401, 1978.
How about the following problem:
Given an integer $n$, how many ways are there to write it as the sum of $k$ squares? Or, equivalently, in $\mathbb{R}^k$, how many lattice points (in the standard integer lattice $\mathbb{Z}^k$) are there on a sphere of radius $\sqrt{n}$? We call the answer $r_k(n)$.
Trial and error methods are obviously rather slow. The standard approach links these numbers to modular forms and it takes the cleanest form if $k$ is divisible by $4$. For $k=4$ and $k=8$ these modular forms are Eisenstein series and one can compute $r_k(n)$ as the sum of powers of divisors of $n$. For $k\geq 12$, the relevant modular forms are no longer Eisenstein series. For example, for $k=24$ one gets an expression in terms of Eisenstein series and the modular form $\Delta$. Thus, to calculate $r_{24}(n)$ one must be able to efficiently calculate the Fourier coefficients of $\Delta$, i.e. the Ramanujan $\tau$-function. (For this story see Mazur's Finding meaning in error terms or Varma's Master Thesis.)
Both the sum of divisor functions appearing in the Fourier expansion of Eisenstein series and the Ramanujan $\tau$-function are multiplicative, so one can restrict to the case of a prime power $p^a$ (as soon as one has compute a prime factorization of $n$). Sum of divisor functions on $p^a$ are easy to calculate and $\tau(p^a)$ can inductively calculated from $\tau(p)$.
For the calculation of $\tau(p)$ there are very sophisticated and very fast algorithms. There is a whole book by Edixhoven, Couveignes, de Jong, Merkl and Bosman devoted to the topic. A related probabilistic algorithm is described in a paper by Zeng and Yin. The running time is polynomial in the logarithm of $p$. This is remarkably fast! It appears that in 2003 the fastest known (probabilistic) algorithm ran in $O(p^{1/2+\varepsilon})$.
I'm not expert on the methods, but they (i.e. Edixhoven,... and Zeng and Yin) appear to use a lot of arithmetic geometry. The use of the Ramanujan conjecture (proven by Deligne and relying on the Weil conjectures) alone would already qualify as deep.
The hydra game. Is a problem about finite trees and any algorithm will work, but "any proof technique that proves [this] is strong enough to prove that Peano arithmetic is consistent".
Given integers $z\geq 1$ and $n\geq 3$, the following algorithm finds all solutions $(x,y)$ in positive integers to $x^n+y^n=z^n$: simply output "no solutions."
(1) Does Babai's http://people.cs.uchicago.edu/~laci/quasipoly.html which gives $\mathsf{GI}\in\mathsf{DTIME}\left(2^{\left(\log n\right)^c}\right)$ at some $c>0$ example work?
(2) Communication complexity of two parties is bounded asymptotically by square root of rank (http://eccc.hpi-web.de/report/2013/084/download/) of the characteristic matrix of the function they are computing uses discrepancy theory and is fairly hidden from a superficial view.
(3) Advanced matrix multiplication algorithms uses additive combinatorics and representation theory which can be called advanced.
(4) No one knew deep learning could be feasible until some people showed its effectiveness in $2000$s. I believe people still do not have a valid mathematical explanation.
What is deep in your philosophical view?
What about the AKS primality test? Years ago Avi Wigderson gave a talk at the Newton Institute of Mathematical Sciences at Cambridge and he related the result to his general method of converting a hard random algorithm into a deterministic one.
There is an "algorithm" for computing the Mordell-Weil group of an elliptic curve, but it requires the (weak) Birch-Swinnerton-Dyer conjecture or the finiteness (of an $\ell$-primary component) of Sha to prove that it terminates.
Integration of algebraic functions. To obtain a complete algorithm for deciding if there is a so-called elementary integral, you need to decide if a given divisor is torsion or not. The program for this is not difficult to implement, but to prove that it works, you need to understand why "good reduction mod p" preserves the order of a torsion divisor (see also Section 6.2 in the PhD thesis of Barry Trager). Someone working in algebraic geometry might not view this as a "deep" result but still, it is well beyond the math one would encounter in computer science classes. In contrast, the transcendental part of the Risch integration algorithm can be explained to students with much less math background.
I don't know if Compressed Sensing can be considered an "algorithm" in the sense of this question. It is a recent signal processing technique used to acquire a sparse signal by means of far fewer measurements than those required by the classic Shannon-Nyquist theorem.
Its analysis involves concepts from advanced probability theory, harmonic analysis, and nonlinear approximation. In my opinion, it is a wonderful chapter of (applied) mathematics.
Very essential bibliography
David L. Donoho, MR 2241189 Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289--1306.
Simon Foucart and Holger Rauhut, MR 3100033 A mathematical introduction to compressive sensing, ISBN: 978-0-8176-4947-0; 978-0-8176-4948-7.
I would like to give neural network as an example. It is quite hard to show convergence to a solution, and it is hard to understand why they sometimes are completely wrong.
Still they are widely used.
One can easily implement an algorithm to fit a $\operatorname{GARCH}(p,q)$ model with standard software such as R. Even a one-step $\operatorname{ARMA}$$\operatorname{-GARCH}$ model (where the $\operatorname{GARCH}$-process is on the residuals) can be implemented but the results of the (strong) consistency of the (Quasi-)MLE require assumptions that are hard to check and the proofs require quite an extensive toolbox, including Random Iterated Lipschitz Maps and exponential almost sure stability since the recursions and the models behind are non-linear.
Many naive factoring algorithms rely on the fact that for every prime p, there is a prime between p and $p^2$. Of course it's usually easy to make a slight modification that removes that requirement.
It's not difficult to write an algorithm that will find a primitive root of a prime p. But without the theorem that every prime has a primitive root, you'd have to write an algorithm that either finds a primitive root, or proves that non exists.
Gazillions of inexperienced programmers write at some time in their life a program that tries to find counter examples to the Collatz conjecture. And inevitably these programs rely on the theorem that the Collatz sequence with any starting value > 1 never has an element ≥ $2^k$, typically for k = 31, 32, 63, or 64. Which is a problem, since that theorem isn't actually true :-).
It depends on what kind of algorithms you need.
A lot of approximation algeorithms need advanced mathematical technics to prove their currectness (to show that the output is a good approximation of the optimum).
Here is a survery on randomized rounding methods in approximation-algorithm: http://homepage.divms.uiowa.edu/~sriram/196/fall08/rr-final.pdf
In addition, there are algorithms that based on some combinatorial constructions which may be relies on advanced math.
Here is a link to an "old" course on Pseudorandomness and Combinatorial Constructions: https://people.eecs.berkeley.edu/~luca/pacc/.
Fermat's last theorem:
No integers exist for a, b and c to satisfy: $$ a^n = b^n + c^n $$ For any values of n > 2.