Worst-case complexity of the optimal LLL algorithm
From MaRDI portal
The author discusses the complexity of the LLL lattice basic reduction algorithm in case of approximation parameter \(\delta\) has the extreme value one (instead of \(2/\sqrt{3}\), as usual). For fixed dimensions he obtains better bounds on the running time of the algorithm than previously known. He shows that the number of iterations is then linear with respect to the size of the input vectors. For the entire collection see [Zbl 0935.00049].
Recommendations
- Analysis of the upper bound on the complexity of LLL algorithm
- Fixed Complexity LLL Algorithm
- An LLL algorithm with quadratic complexity
- Worst-case complexity, average-case complexity and lattice problems
- An upper bound on the average number of iterations of the LLL algorithm
- scientific article; zbMATH DE number 1094170
- scientific article; zbMATH DE number 4024619
- Worst case complexity of direct search under convexity
- On the optimal order of worst case complexity of direct search
- The LLL algorithm and integer programming
Cited in
(7)- An upper bound on the average number of iterations of the LLL algorithm
- The optimal LLL algorithm is still polynomial in fixed dimension.
- A physical study of the LLL algorithm
- On the optimal order of worst case complexity of direct search
- Analysis of the upper bound on the complexity of LLL algorithm
- scientific article; zbMATH DE number 1094170 (Why is no real title available?)
- Worst case complexity of direct search under convexity
This page was built for publication: Worst-case complexity of the optimal LLL algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4508391)
