Timeline for Examples of algorithms requiring deep mathematics to prove correctness
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 4, 2021 at 2:43 | vote | accept | Gorka | ||
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jul 17, 2016 at 16:03 | comment | added | John Jiang | 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. | |
| Jul 17, 2016 at 2:18 | comment | added | Sasho Nikolov | @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? | |
| Jul 16, 2016 at 21:07 | comment | added | John Jiang | The third item seems to be difficult only when you try to analyze its runtime. | |
| Jul 16, 2016 at 17:45 | history | edited | Sasho Nikolov | CC BY-SA 3.0 |
added 6 characters in body
|
| Jul 13, 2016 at 23:20 | history | edited | Sasho Nikolov | CC BY-SA 3.0 |
added 49 characters in body
|
| S Jul 13, 2016 at 23:15 | history | answered | Sasho Nikolov | CC BY-SA 3.0 | |
| S Jul 13, 2016 at 23:15 | history | made wiki | Post Made Community Wiki by Sasho Nikolov |