Seungki Kim - University of Cincinnati
Date/Time/Location
Thursday, May 8th, 2025, 12:10 pm; Hill Center 705
A physical study of the LLL algorithm
The Lenstra-Lenstra-Lovasz (LLL) algorithm is a celebrated and fundamental method of lattice reduction, which finds in polynomial time a reasonably short vector of a lattice in a Euclidean space. Understanding its behavior in practice has real-world consequences, as the internet's migration to post-quantum cryptography has recently begun, and lattice reduction, if powerful enough, can break it. Surprisingly, it turns out to be extremely fruitful to interpret LLL as a 1-d sandpile model and study it as such. We discuss this work and the related pilot studies, as well as several unanswered questions that statistical physics may help with.