Non-abelian analogs of lattice rounding

Evgeni Begelfor, Stephen D. Miller, Ramarathnam Venkatesan

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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

Original languageEnglish (US)
Pages (from-to)117-133
Number of pages17
JournalGroups, Complexity, Cryptology
Volume7
Issue number2
DOIs
StatePublished - Nov 1 2015

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

Keywords

  • Lattice rounding
  • Lyapunov exponents
  • inapproximability
  • matrix groups
  • norm concentration
  • word problems

Fingerprint

Dive into the research topics of 'Non-abelian analogs of lattice rounding'. Together they form a unique fingerprint.

Cite this