Non-Abelian Analogs of Lattice Rounding
This work addresses foundational challenges in computational algebra and cryptography by extending lattice-based methods to non-abelian settings, though it appears incremental as it builds on existing lattice rounding concepts.
The paper tackles the problem of generalizing lattice rounding to non-abelian matrix groups, developing an algorithm for a normed word problem with random inputs and proving an inapproximability result that limits strong approximation algorithms similar to LLL.
Lattice rounding in Euclidean space can be viewed as finding the nearest point in the orbit of an action by a discrete group, relative to the norm inherited from the ambient space. Using this point of view, we initiate the study of non-abelian analogs of lattice rounding involving matrix groups. In one direction, we give an algorithm for solving a normed word problem when the inputs are random products over a basis set, and give theoretical justification for its success. In another direction, we prove a general inapproximability result which essentially rules out strong approximation algorithms (i.e., whose approximation factors depend only on dimension) analogous to LLL in the general case.