Search papers, labs, and topics across Lattice.
This paper analyzes lattice reduction algorithms through the lens of majorization theory, revealing that Lov谩sz swaps act as T-transforms that decrease Schur-convex measures of the Gram-Schmidt profile spread. This perspective yields a variational interpretation of the worst-case Gram-Schmidt orthogonalization (GSA) envelope and an exact telescoping identity for variance dissipation in swap trajectories. Furthermore, the authors leverage this framework to develop Thermal-Adaptive and Geodesic Deep-LLL heuristics that improve performance on flat and structured lattices, respectively.
Lattice reduction, long a dark art, can now be understood as minimizing variance in a Gram-Schmidt profile, leading to new, efficient heuristics.
Lattice reduction smooths the Gram-Schmidt profile, and we use majorization to describe the local swap mechanism behind that smoothing. In this language, each non-degenerate Lov\'asz swap acts as a T-transform on the log-norm profile. As a consequence, every strictly Schur-convex measure of profile spread decreases at such a swap. Two structural consequences follow. First, the worst-case GSA envelope admits a variational interpretation. It is the unique minimum-variance profile compatible with the Lov\'asz gap geometry, so its slope is determined by the LLL parameter alone. Second, the realized swap trajectory satisfies an exact telescoping identity for variance dissipation. The same viewpoint also helps organize deep-insertion heuristics. It suggests a thermal family of Schur-convex scoring rules, motivates adaptive selection within that family, and leads to two concrete selectors: Thermal-Adaptive, which reduces operation counts relative to SS-GG on flat profiles in our benchmarks while recovering SS-GG on $q$-ary inputs, and Geodesic Deep-LLL, which reduces equivalent-swap counts on structured lattices in our benchmarks at higher wall-clock cost.
