Tata Institute of Fundamental Research
LLL Algorithm
STCS Student Seminar
Speaker:
Koduri Choudary (TIFR)
Organiser:
Ashutosh Shankar
Date:
Friday, 18 Oct 2024, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The Shortest Vector Problem SVP (closest point to origin in a lattice of finite basis) is considered to be hard. The LLL algorithm, (developed by A.K. Lenstra, H.W. Lenstra Jr., and L. Lovasz) gives an approximate solution to the SVP in polynomial time on the input size i.e. description of lattice basis with an approximation factor (4/3)^(n/2) where n is the dimension of the lattice.
This algorithm is a generalisation of the SVP algorithm given by Gauss in 1801 for 2 dimensions.
Paper:
https://www.researchgate.net/publication/50863306_Factoring_Polynomials_with_Rational_Coefficients
| Speaker: | Koduri Choudary (TIFR) |
| Organiser: | Ashutosh Shankar |
| Date: | Friday, 18 Oct 2024, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The Shortest Vector Problem SVP (closest point to origin in a lattice of finite basis) is considered to be hard. The LLL algorithm, (developed by A.K. Lenstra, H.W. Lenstra Jr., and L. Lovasz) gives an approximate solution to the SVP in polynomial time on the input size i.e. description of lattice basis with an approximation factor (4/3)^(n/2) where n is the dimension of the lattice.
This algorithm is a generalisation of the SVP algorithm given by Gauss in 1801 for 2 dimensions.
Paper:
https://www.researchgate.net/publication/50863306_Factoring_Polynomials_with_Rational_Coefficients