Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: List Decoding Barnes-Wall Lattices   The question of list decoding error-correcting codes over finite fields
(under the Hamming metric) has been widely studied in recent years. Motivated
by the similar discrete structure of linear codes and point lattices in R^N,
and their many shared applications across complexity theory, cryptography, and
coding theory, we initiate the study of list decoding for lattices. Namely: for
a lattice L in R^N, given a target vector r in R^N and a distance parameter d,
output the set of all lattice points w in L that are within distance d of r.
  In this work we focus on combinatorial and algorithmic questions related to
list decoding for the well-studied family of Barnes-Wall lattices. Our main
contributions are twofold:
  1) We give tight (up to polynomials) combinatorial bounds on the worst-case
list size, showing it to be polynomial in the lattice dimension for any error
radius bounded away from the lattice's minimum distance (in the Euclidean
norm).
  2) Building on the unique decoding algorithm of Micciancio and Nicolosi (ISIT
'08), we give a list-decoding algorithm that runs in time polynomial in the
lattice dimension and worst-case list size, for any error radius. Moreover, our
algorithm is highly parallelizable, and with sufficiently many processors can
run in parallel time only poly-logarithmic in the lattice dimension.
  In particular, our results imply a polynomial-time list-decoding algorithm
for any error radius bounded away from the minimum distance, thus beating a
typical barrier for error-correcting codes posed by the Johnson radius.

0
The categories of this paper are: hep-ph
27
The categories of this paper are: comp-gas
16
The categories of this paper are: stat
14
The categories of this paper are: math-ph
17
The categories of this paper are: q-fin
13
The categories of this paper are: quant-ph
28
The categories of this paper are: alg-geom
21
The categories of this paper are: adap-org
36
The categories of this paper are: cmp-lg
26
The categories of this paper are: bayes-an
15
The categories of this paper are: nucl-ex
7
The categories of this paper are: hep-th
37
The categories of this paper are: supr-con
33
The categories of this paper are: plasm-ph
19
The categories of this paper are: eess
12
The categories of this paper are: nucl-th