A physical study of the LLL algorithm
This work applies to LLL some methods of statistical physics that are typically used to study SOC models, or more colloquially, sandpile models. Such effort is justified by the close similarity in numerous aspects of the quantitative behavior of both algorithms/systems. There are two merits to our approach:
(i) The sandpile analogues of LLL allow rigorous mathematical studies of its RHF and time complexity to some extent.
(ii) The formulas from the finite-size scaling theory have a number of interesting implications on the output profile of LLL — GSA, average RHF and its variance, and so on.
This is a joint work with Jintai Ding (Tsinghua), Tsuyoshi Takagi (U. Tokyo), Yuntao Wang (Osaka) and Bo-Yin Yang (Academia Sinica).