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.
$\begingroup$
$\endgroup$
8
-
3$\begingroup$ Do you have any example in mind? $\endgroup$– WojowuCommented Jul 12, 2016 at 20:12
-
4$\begingroup$ @Wojowu The question is providing examples... $\endgroup$– Federico PoloniCommented Jul 12, 2016 at 20:31
-
4$\begingroup$ @FedericoPoloni Generally when this kind of question is asked, then OP knows an example of what he is looking for and is looking for more of this. I am hence wondering whether this is the case here as well. $\endgroup$– WojowuCommented Jul 12, 2016 at 20:32
-
8$\begingroup$ The algorithm for finding the rank of an elliptic curve via repeated 2-descent is only proved to terminate if the 2-power part of sha is finite, so this requires as yet unproved mathematics in general! $\endgroup$– zntCommented Jul 12, 2016 at 20:33
-
12$\begingroup$ Many derandomization algorithms start with "let $G$ be an expander graph". Explicit construction of expanders depends (classically) on Kazhdan's property $(T)$. $\endgroup$– AsafCommented Jul 12, 2016 at 20:33
|
Show 3 more comments
17 Answers
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ The third item seems to be difficult only when you try to analyze its runtime. $\endgroup$ Commented Jul 16, 2016 at 21:07
-
1$\begingroup$ @JohnJiang I have a similar comment to this as my comment about Miller's primality testing algorithm: since I don't think there is a known algorithmic way to tell when the Markov chain is sufficiently mixed, we just run it for a fixed number of steps, and then the Cheeger constant is used to analyze the approximation guarantee, which is part of correctness. In a way, there is a duality between approximation and running time here: if you fix one, you need to use mixing time analysis to bound the other. Why distinguish them? $\endgroup$ Commented Jul 17, 2016 at 2:18
-
1$\begingroup$ that makes sense. I was making an incorrect analogy with deterministic algorithm. There are then many such based on MCMC, such as Glauber dynamics on Ising model at critical temperature, which requires the use of SLE theory. $\endgroup$ Commented Jul 17, 2016 at 16:03
$\begingroup$
$\endgroup$
8
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.
-
3$\begingroup$ Shouldn't that be $O((\log n)^4)$ possibly with some additional $\log \log$ factors? Also it's the probabilistic M-R that's practical and widely-used, and that doesn't depend on GRH. The deterministic one depends on GRH and it's supposedly slower in practice than ECPP and other deterministic algorithms. $\endgroup$ Commented Jul 13, 2016 at 3:32
-
1$\begingroup$ Fair enough, the running time is indeed $O((\log n)^2 \cdot (\log n)^{2 + \varepsilon})$ with the first $2$ coming from the Generalized Riemann Hypothesis. Note that in reality the $2$ is a $1$, although we can't prove it even on GRH. Yes, the probabilistic version is what is really used in practice (unless you want to prove primality assuming GRH). In any case isn't the running time of ECPP just a heuristic, and the worst case still a bit slower than Miller-Rabin? (or as good). Either way ECPP would also be a good example to OP's question... $\endgroup$ Commented Jul 13, 2016 at 5:40
-
5$\begingroup$ The question is about proving correctness of the algorithm, not running time. I don't see how these are related. $\endgroup$ Commented Jul 13, 2016 at 12:49
-
5$\begingroup$ @JanneKokkala: Well without the bound provided by GRH, the algorithm would be utterly worthless since the runtime would be exponential (in $\log n$). $O(n)$ where $n$ is some huge 2048+ bit prime is not even what I'd call an algorithm. $\endgroup$ Commented Jul 13, 2016 at 13:22
-
11$\begingroup$ @JanneKokkala Miller's algorithm checks all integers up to $O(\log n)^2$ for certificates of composite-ness. GRH is used to prove that if no certificate is found in that range then $n$ is prime, so it is in fact used in the proof of correctness. The point is that the algorithm needs to know when to stop searching: this affects running time, but an incorrect stopping condition would affect correctness too. $\endgroup$ Commented Jul 13, 2016 at 23:37
$\begingroup$
$\endgroup$
1
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.
-
4$\begingroup$ Does this find a generator for every rank 1 elliptic curve? That is, do we know we can quickly find such a $P$ for which $Q$ is not a torsion point? And actually, does the algorithm really rely on Gross-Zagier and Kolyvagin, if we assume from the outset that the curve has rank 1? $\endgroup$ Commented Jul 13, 2016 at 2:58
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ I dont know much about this, but I think there are other examples of cool math in property testing algorithms: graph limits, Gowers norms.. $\endgroup$ Commented Jul 13, 2016 at 23:13
-
1$\begingroup$ Oh that, for sure -- I picked only one, but there are plenty... a quick lookup, for instance, shows that the Robertson-Seymour theorem was used to show that "any minor-closed graph property is testable in constant time in the bounded degree model." (A. Hassidim, J. A. Kelner, H. N. Nguyen and K. Onak, "Local Graph Partitions for Approximation and Testing," FOCS '09) $\endgroup$ Commented Jul 13, 2016 at 23:30
$\begingroup$
$\endgroup$
3
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.
-
2$\begingroup$ and proving $\tau$ is multiplicative is quite.. complicated, no ? $\endgroup$– reunsCommented Jul 13, 2016 at 23:23
-
1$\begingroup$ It is not obvious, but follows quite easily from the theory of Hecke operators. This is certainly not on a comparable level of depth to many other things these people use. $\endgroup$ Commented Jul 14, 2016 at 16:20
-
$\begingroup$ The multiplicativity of $\tau$ was conjectured by Ramanujan, and eventually proved by Mordell using the operators he discovered (now called Hecke operators). This is not hard if you consider this technology "well-known", but required non-trivial innovation from Mordell. $\endgroup$ Commented Jul 16, 2016 at 18:28
$\begingroup$
$\endgroup$
3
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".
-
-
$\begingroup$ Well, proving the result "any proof technique that proves [this] is strong enough" requires deep mathematics, but proving that the hydra game terminates only requires elementary results about ordinals in ZF. I guess to some (most?) computer science courses even the word "ordinal" is already "deep mathematics". But computer scientists are pretty much using a system equivalent to ZF, and hence powerful enough to prove that Peano arithmetic is consistent, even if they don't call it that and can't quote the axioms. $\endgroup$ Commented Jul 17, 2016 at 12:03
-
12$\begingroup$ @SteveJessop I don't understand the condescending comments about computer scientists. There is a long history of applying tools from logic and model theory in theoretical computer science, going back to the beginning of the field, with conferences and journals dedicated to the topic. Of course, you don't talk about ordinals in an undergraduate data structures course, but you wouldn't do that in Calculus I, either. $\endgroup$ Commented Jul 19, 2016 at 14:55
$\begingroup$
$\endgroup$
2
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$\begingroup$ thank you, although I was looking for an algorithm which would actually be used. $\endgroup$– GorkaCommented Jul 14, 2016 at 3:11
-
2$\begingroup$ This is actually used: whenever you are asked to solve a Diophantine equation that reduces to a special case of Fermat's Last Theorem, you can reply that there are no solutions. $\endgroup$ Commented Jul 14, 2016 at 20:07
$\begingroup$
$\endgroup$
2
(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?
-
1$\begingroup$ I think so, I am failing to understand it so I guess. Thank you. $\endgroup$– GorkaCommented Jul 12, 2016 at 21:04
-
1$\begingroup$ "deep learning algorithms may be employing a generalized RG-like scheme to learn relevant features from data": arxiv.org/abs/1410.3831 $\endgroup$ Commented Jul 13, 2016 at 12:21
$\begingroup$
$\endgroup$
4
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.
-
14$\begingroup$ I am not sure this is a good example: the analysis of AKS uses mostly basic number theory, accessible to advanced undegrads, which is one of the amazing things about it. K and S in AKS were undergrads at the time the paper was written. $\endgroup$ Commented Jul 13, 2016 at 0:19
-
1$\begingroup$ Wrong: while the correctness of the AKS algorithm is elementary, its running time bounds depend on on serious analytic number theory (they used results of Fouvry). $\endgroup$ Commented Jul 16, 2016 at 18:38
-
$\begingroup$ @LiorSilberman thanks for the correction! $\endgroup$ Commented Jul 19, 2016 at 14:55
-
2$\begingroup$ @LiorSilberman, in the linked version of the paper the polynomial-time result is achieved with elementary methods. The results of Fouvry are only used to get the degree of the polynomial-time function from 21/2 down to 15/2, and were used more heavily in prior versions of the proofs. The current proof is a good example for using deep mathematics along the way, but not needing it in the end. $\endgroup$– user44143Commented Jul 20, 2016 at 11:28
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.
-
2$\begingroup$ I don't think this fits well, because so far deep mathematics doesn't have much to say about when these models will and won't work. $\endgroup$ Commented Jul 14, 2016 at 10:27
-
$\begingroup$ Thanks for the link to the paper. It's going to be a very interesting read. $\endgroup$ Commented Jul 15, 2016 at 15:27
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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 :-).
$\begingroup$
$\endgroup$
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/.
$\begingroup$
$\endgroup$
3
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.
-
3$\begingroup$ yes, this was already covered in another post. $\endgroup$– GorkaCommented Jul 14, 2016 at 15:05
-
$\begingroup$ What's this have to do with an algorithm? I just see a proof that there is none. That seems a bit useless, we have a proof that there is no polynomial deg > 0 without a root in C, no solution in radicals to specific quintic equations, no prime 1 mod 4 that can't be written as the sum of 2 squares, and hence no algorithms to find these objects, or else the algorithm "return false" trivially executes by way of a mathematical proof. $\endgroup$– djechlinCommented Jul 16, 2016 at 16:02
-
$\begingroup$ @djechlin: see Richard Stanley's answer. Any theorem that something doesn't exist (in this case a solution to an equation), is also a proof of the correctness of the trivial algorithm "HALT" for solving the problem "list all the somethings" (in this case find the solutions to the equation). And vice-versa: proving the correctness of that algorithm proves non-existence, so if the only known proofs of the theorem use deep mathematics then the only known proofs that the algorithm is correct are deep too. It's a lateral-thinking answer to the question: HALT is uninteresting as an algorithm. $\endgroup$ Commented Jul 17, 2016 at 12:13