You are looking at a specific version 20150112:072824 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
lattice roundingmatrix groupsnorm concentrationLyapunov exponentsword problemsinapproximability
Contact author(s)
miller @ math rutgers edu
History
2015-01-12: received
Short URL
https://ia.cr/2015/024
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.