Covering Convex Bodies and the Closest Vector Problem. [PDF]
Discrete Comput Geom, 2022 We present algorithms for the [Formula: see text] -approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms in dimension n has running time of [Formula: see text] .
Naszódi M, Venzin M.
europepmc +13 more sources
Covering Cubes and the Closest Vector Problem [PDF]
Proceedings of the twenty-seventh annual symposium on Computational geometry, 2011 We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest vector problem in the infinity-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2^(O(n))(log(1 ...
Eisenbrand, Friedrich +2 more
core +5 more sources
A closest vector problem arising in radiation therapy planning [PDF]
Journal of Combinatorial Optimization, 2011 In this paper we consider the following closest vector problem. We are given a set of 0-1 vectors, the generators, an integer vector, the target vector, and a nonnegative integer C.
Engelbeen, Céline +4 more
core +8 more sources
Improved Algorithms for the Shortest Vector Problem and the Closest Vector Problem in the Infinity Norm [PDF]
, 2018 Ajtai, Kumar and Sivakumar [Ajtai et al., 2001] gave the first 2^O(n) algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices.
Mukhopadhyay, Priyanka, Aggarwal, Divesh
core +6 more sources
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing
SIAM Journal on Computing, 2014 We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n).
Popat, Preyas +2 more
core +2 more sources
Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward [PDF]
IEEE Transactions on Information Theory, 2017 A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2 ...
Gastpar, Michael C., Sahraei, Saeid
core +5 more sources
A Parametric Version of LLL and Some Consequences: Parametric Shortest and Closest Vector Problems [PDF]
SIAM Journal on Discrete Mathematics, 2020 Given a parametric lattice with a basis given by polynomials in $\Bbb{Z}[t]$, we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in $t$: that is, they are given by formulas that are piecewise polynomial ...
Goodrick, John +5 more
core +4 more sources
The closest vector problem in tensored root lattices of type A and in their duals [PDF]
Designs, Codes and Cryptography, 2017 In this work we consider the closest vector problem (CVP)—a problem also known as maximum-likelihood decoding—in the tensor of two root lattices of type A ((Formula presented.)), as well as in their duals ((Formula presented.)).
van Woerden, W.P.J. (Wessel P. J.) +1 more
core +5 more sources
A Linear-Time Algorithm for the Closest Vector Problem of Triangular Lattices
CoRRFuzzy Extractor (FE) and Fuzzy Signature (FS) are useful schemes for generating cryptographic keys from fuzzy data such as biometric features. Several techniques have been proposed to implement FE and FS for fuzzy data in an Euclidean space, such as ...
Nakamura, Wataru, Takahashi, Kenta
core +4 more sources
Qubo model for the Closest Vector Problem
CoRR, 2023 In this paper we consider the closest vector problem (CVP) for lattices $Λ\subseteq \mathbb{Z}^n$ given by a generator matrix $A\in \mathcal{M}_{n\times n}(\mathbb{Z})$. Let $b>0$ be the maximum of the absolute values of the entries of the matrix $A$.
Eduardo Canale +2 more
openaire +2 more sources