Cryptology ePrint Archive: Report 2015/024

Non-Abelian Analogs of Lattice Rounding

Evgeni Begelfor and Stephen D. Miller and Ramarathnam Venkatesan

Abstract: 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.

Category / Keywords: foundations / lattice rounding, matrix groups, norm concentration, Lyapunov exponents, word problems, inapproximability

Date: received 11 Jan 2015

Contact author: miller at math rutgers edu

Available format(s): PDF | BibTeX Citation

Version: 20150112:072824 (All versions of this report)

Short URL: ia.cr/2015/024

Discussion forum: Show discussion | Start new discussion