Timeline for Correctness of AKS algorithm for shortest vector problem
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 12, 2019 at 15:00 | history | tweeted | twitter.com/StackCSTheory/status/1138823457267953664 | ||
| Jun 12, 2019 at 5:46 | vote | accept | Hilder Vitor Lima Pereira | ||
| Jun 12, 2019 at 2:38 | answer | added | Sasho Nikolov | timeline score: 6 | |
| Jun 11, 2019 at 6:44 | comment | added | Hilder Vitor Lima Pereira | Oh, I see. So I misread it. Thank you very much for your comments. If you want to turn it into an answer, feel free to do so. Now what is puzzling me is the fact that if we play differently with the tossing probability (for instance, applying $\tau$ to all $x_i$), then the distribution of $x_i$ is still uniform, but the correctness of the algorithm is no longer guaranteed. Hence, the number of sampled points $x_i$ and their distribution are not enough to prove correctness and therefore it depends on something not controlled by the algorithm (the way we toss the points in the analysis)... | |
| Jun 10, 2019 at 17:00 | comment | added | Sasho Nikolov | It's not true that all gree points are flipped. He says "After choosing each $x_i$, we toss a fair coin and if it comes up heads, we replace $x_i$ with $\tau(x_i)$". Think of every point $x_i$ as having a coin attached to it. Before you use $x_i$, you toss the coin to decide whether to keep $x_i$ as $x_i$ or to replace it by $\tau(x_i)$. This is done independently for each $x_i$. | |
| Jun 10, 2019 at 8:13 | comment | added | Hilder Vitor Lima Pereira | No really... Because at this part of the notes, Regev is referring only to the "green" points, that is, points that are already in $C_1 \cup C_2$, and all those points must be flipped (by the definition of the function $\tau$). And even if we considered all points instead of only the green ones, the probability that it is not flipped should be $\frac{Vol(B(0,2) \setminus C_1 \cup C_2)}{Vol(B(0,2))}$, shouldn't it? | |
| Jun 9, 2019 at 21:13 | comment | added | Sasho Nikolov | Each vector is tossed independently, so, on average, half the vectors $x_i$ will flip from $C_1$ to $C_2$, or vice versa, an the other half will stay put. Does that answer your question? | |
| Jun 9, 2019 at 15:19 | history | asked | Hilder Vitor Lima Pereira | CC BY-SA 4.0 |