Timeline for Theorems that are essentially impossible to guess by empirical observation
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2022 at 17:26 | history | edited | Timothy Chow | CC BY-SA 4.0 |
Added link to blog post by David Eppstein
|
| Dec 30, 2021 at 14:04 | history | edited | Timothy Chow | CC BY-SA 4.0 |
Added example involving the Lovasz Local Lemma
|
| Dec 30, 2021 at 2:20 | comment | added | Will Sawin | Part of my point is just that "small numbers can be deceiving" works both ways - it takes a while before $\sqrt{\log n}$ becomes bigger than $6$! (If the randomized algorithm just barely fails one can do a local search - e.g. look for one $i$ such that flipping $\epsilon_i$ lowers the $\ell^{\infty}$-norm, and then iterate until reaching a local minimum. This is even harder to analyze rigorously but often effective in practice.) I don't deny that surely some example in that paper is hard to find in practice. | |
| Dec 30, 2021 at 0:39 | comment | added | Timothy Chow | @WillSawin I peeked at Spencer's paper. It seems that the naive idea of choosing random signs easily gives a provable guarantee with an extra factor of $\sqrt{\ln n}$. Maybe in practice the algorithm works better than that. I guess I should have picked a Lovasz Local Lemma example or something to better make my point. | |
| Dec 30, 2021 at 0:31 | comment | added | Timothy Chow | @WillSawin It's certainly not true in general that random generation works for the examples in Alon's paper. For example the Lovasz Local Lemma usually gives you exponentially rare objects. But maybe you are right about Spencer's result in particular; I admit I didn't think too hard about whether there is an easy randomized algorithm that appears to work in practice but doesn't have a provable guarantee. | |
| Dec 30, 2021 at 0:28 | comment | added | Will Sawin | For this example, if you choose the $\epsilon_i$ at random, the coordinates of the sum will be approximately Gaussian-distributed, so you're looking for examples of $n$ samples without $6$-sigma deviations, which should be easy to find for $n$ at most a million or so. | |
| Dec 30, 2021 at 0:27 | comment | added | Will Sawin | I actually disagree. In many similar ones (e.g. Ramanujan graphs) there are nonconstructive existence results but, separately, it's IIRC relatively easy to find examples by generating objects at random and throwing out the ones that don't have the desired property, because a high proportion empirically have that property. | |
| Dec 30, 2021 at 0:18 | history | edited | Timothy Chow | CC BY-SA 4.0 |
Added example of combinatorial designs
|
| S Dec 30, 2021 at 0:12 | history | answered | Timothy Chow | CC BY-SA 4.0 | |
| S Dec 30, 2021 at 0:12 | history | made wiki | Post Made Community Wiki by Timothy Chow |