Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding a closest point in a lattice of Voronois first kind
599
0
0.0
(
0
)
Added by
Robert McKilliam
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We show that for those lattices of Voronois first kind with known obtuse superbasis, a closest lattice point can be computed in $O(n^4)$ operations where $n$ is the dimension of the lattice. To achieve this a series of relevant lattice vectors that converges to a closest lattice point is found. We show that the series converges after at most $n$ terms. Each vector in the series can be efficiently computed in $O(n^3)$ operations using an algorithm to compute a minimum cut in an undirected flow network.
rate research
Read More
We consider the problem of finding the closest lattice point to a vector in n-dimensional Euclidean space when each component of the vector is available at a distinct node in a network. Our objectives are (i) minimize the communication cost and (ii) obtain the error probability. The approximate closest lattice point considered here is the one obtained using the nearest-plane (Babai) algorithm. Assuming a triangular special basis for the lattice, we develop communication-efficient protocols for computing the approximate lattice point and determine the communication cost for lattices of dimension n>1. Based on available parameterizations of reduced bases, we determine the error probability of the nearest plane algorithm for two dimensional lattices analytically, and present a computational error estimation algorithm in three dimensions. For dimensions 2 and 3, our results show that the error probability increases with the packing density of the lattice.
Permutation polynomials have many applications in finite fields theory, coding theory, cryptography, combinatorial design, communication theory, and so on. Permutation binomials of the form $x^{r}(x^{q-1}+a)$ over $mathbb{F}_{q^2}$ have been studied before, K. Li, L. Qu and X. Chen proved that they are permutation polynomials if and only if $r=1$ and $a^{q+1} ot=1$. In this paper, we consider the same binomial, but over finite fields $mathbb{F}_{q^3}$ and $mathbb{F}_{q^e}$. Two different kinds of methods are employed, and some partial results are obtained for them.
We consider the closest lattice point problem in a distributed network setting and study the communication cost and the error probability for computing an approximate nearest lattice point, using the nearest-plane algorithm, due to Babai. Two distinct communication models, centralized and interactive, are considered. The importance of proper basis selection is addressed. Assuming a reduced basis for a two-dimensional lattice, we determine the approximation error of the nearest plane algorithm. The communication cost for determining the Babai point, or equivalently, for constructing the rectangular nearest-plane partition, is calculated in the interactive setting. For the centralized model, an algorithm is presented for reducing the communication cost of the nearest plane algorithm in an arbitrary number of dimensions.
The lattice $A_n^*$ is an important lattice because of its covering properties in low dimensions. Clarkson cite{Clarkson1999:Anstar} described an algorithm to compute the nearest lattice point in $A_n^*$ that requires $O(nlog{n})$ arithmetic operations. In this paper, we describe a new algorithm. While the complexity is still $O(nlog{n})$, it is significantly simpler to describe and verify. In practice, we find that the new algorithm also runs faster.
The paper studies a class of three user Gaussian interference channels. A new layered lattice coding scheme is introduced as a transmission strategy. The use of lattice codes allows for an alignment of the interference observed at each receiver. The layered lattice coding is shown to achieve more than one degree of freedom for a class of interference channels and also achieves rates which are better than the rates obtained using the Han-Kobayashi coding scheme.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
