3
$\begingroup$

We are currently looking for both dense and decodable lattices.

Precisely, we want a lattice which CVP can be solved in polynomial time like $O(n^2)$ or $O(n^3)$ where $n$ is the dimension like 128 or 512.

We have investigated E8 and Leech lattice. Their CVP can be solved efficiently but the dimensions are not high enough.

We also read the SPLAG (sphere packings lattices and groups). We notice they seldom talk about decoding algorithms.

Our current solution is to concatenate lots of Leech lattice.

$\endgroup$
4
  • 1
    $\begingroup$ Have you looked at Noam Elkies's Mordell-Weil lattices? They're defined for power-of-two dimensions and they're record-breakingly dense in the range you describe: citeseerx.ist.psu.edu/viewdoc/… There's a sequel of this paper which looks specifically at the dimension-128 lattice. I don't know whether anyone has tried to solve the closest vector problem in these lattices, though. $\endgroup$ May 19, 2021 at 9:45
  • $\begingroup$ I'm recently looking at the same problem but I find probably leech lattice is the best we have at this moment. BTW I'm curious about your implementation of the CVP for leech lattice. Would you like to share it if you don't mind? $\endgroup$
    – Dan Qiao
    May 25, 2021 at 0:13
  • 1
    $\begingroup$ In a comment under Dan Qiao's answer which is now converted to a comment, the OP answered: "Of course, here is our implementation, which is based on "Soft Decoding Techniques for Codes and Lattices, Including the Golay Code and the Leech Lattice"". $\endgroup$
    – Stefan Kohl
    May 25, 2021 at 7:41
  • $\begingroup$ I'm wondering whether iterative decoding of product codes (some authors call it turbo decoding as the principle is the same) can be adapted to lattices. The catch is that it is not necessarily guaranteed to converge to the closest point, but does so with "high probability". My experience suggests to me that iterative soft decision decoding is fast. I personally tested it with a 3-fold product of the length 16 extended Hamming code, and it worked quite well. Another catch is that as I was working on a telcomm app, I was more interested in a BER vs. SNR curve, which may not mathc your needs. $\endgroup$ Jul 1, 2021 at 11:44

1 Answer 1

1
$\begingroup$

There are a number of sources of high-dimensional lattices that admit efficient CVP algorithms (and a few that admit efficient BDD algorithms, a "promise" version of CVP where one decodes errors contained in $\mathcal{B}_n(\lambda_1(L) / 2)$, e.g. the largest circumscribed sphere within the Voronoi cell of the lattice). I'll briefly summarize some below, before discussing density.

CVP:

  1. If one can efficiently solve CVP on $L$, then one can efficiently solve it on $L\otimes \mathbb{Z}^n \cong \bigoplus_{i = 1}^n L$. It sounds like you have already realized this, but it is worth mentioning explicitly.

  2. The lattices $A_n, A_n^*, D_n, D_n^*$ can all be efficiently decoded (this is mentioned in Conway and Sloane)

  3. A mild generalization of the $A_n, A_n^*$ lattices known as Coxeter lattices admit $O(n)$ CVP algorithms.

BDD:

  1. Barnes-Wall Lattices admit $O(n(\log n)^2)$-time decoding algorithms

  2. A particularly dense family of lattices are the Discrete Logarithm lattices. The precise complexity of BDD on it depends on a number of choices one makes in constructing it, but looks like it can be $o(n^2)$ pretty easily.

There are other dense high-dimensional lattices that admit fairly efficient BDD algorithms (namely Barnes-Sloane lattices, which one can even list decode), but I think these are $\Omega(n^2)$ (but poly-time), although the algorithms are fairly naive, so with further work it is plausible they can be decoded in $o(n^2)$ time.

Of all of these, I believe the densest are the Barnes-Sloane lattices and the Discrete Logarithm lattices, so if you can tolerate a BDD algorithm instead of a CVP algorithm, I would look into the discrete logarithm lattices. If you require CVP algorithms, you should probably look into Coxeter lattices, although I do not know how their density will compare with using direct sums of the leech lattice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.