Paper 2015/024
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)
-
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
-
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},
url = {https://eprint.iacr.org/2015/024}
}
