LLL and stochastic sandpile models
This addresses the unexplained practical aspects of the LLL algorithm for researchers in lattice-based cryptography and computational mathematics, offering a novel theoretical framework.
The paper tackles the problem of understanding the practical behavior of the LLL algorithm by proposing sandpile models from statistical physics that accurately imitate it, and proves key statements about LLL while formulating conjectures for future theory development.
Theaimofthepresentpaperistosuggestthatstatisticalphysicsprovides the correct language to understand the practical behavior of the LLL algorithm, most of which are left unexplained to this day. To this end, we propose sandpile models that imitate LLL with compelling accuracy, and prove for these models some of the most desired statements regarding LLL. We also formulate a few conjectures that formally capture our heuristics and would serve as milestones for further development of the theory.