### Non-Abelian Analogs of Lattice Rounding

Evgeni Begelfor, 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)
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

CC BY

BibTeX

@misc{cryptoeprint:2015/024,
author = {Evgeni Begelfor and Stephen D.  Miller and Ramarathnam Venkatesan},
title = {Non-Abelian Analogs of Lattice Rounding},
howpublished = {Cryptology ePrint Archive, Paper 2015/024},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/024}},
url = {https://eprint.iacr.org/2015/024}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.