3 ms·
H^3 perhaps. There is a precedent. The Lenstra-Lenstra-Lovasz algorithm (LLL) is often called L^3, admittedly because the complexity is O(L^3) in the bit size L
by wbhart 13y ago
H^3 perhaps. There is a precedent. The Lenstra-Lenstra-Lovasz algorithm (LLL) is often called L^3, admittedly because the complexity is O(L^3) in the bit size L. Later a quadratic algorithm was discovered, cheekily called the L^2 algorithm. Later still it was done in quasilinear time. Unfortunately, the authors of those papers did not have the sense to have names starting with L.
- KennyCason 13y agoI definitely like your reasoning for H^3 better than my reasoning for "Triple H," the wrestler :)
- ColinWright 13y agoI was unaware of an L^2 (or better) algorithm - can you provide a reference? Even just a term to search for - my Search-fu is failing. Thanks. Added in edit: OK, I've found these - hoping I'm on the right track: 1982 LLL Lenstra Lenstra Lovász 1987 BKZ Block Korkine Zolotarev 2002 RSR Random Sampling Reduction 2002 PDR Primal Dual Reduction