Authors Daniel Dadush, G{\'a}bor Kun,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34
www.theoryofcomputing.org
Lattice Sparsification and the
Approximate Closest Vector Problem
Daniel Dadush Gábor Kun∗
Received July 11, 2013; Revised January 11, 2016; Published June 16, 2016
Abstract: We give a deterministic algorithm for solving the (1 + ε)-approximate Closest
Vector Problem (CVP) on any n-dimensional lattice and in any near-symmetric norm in
2O(n) (1 + 1/ε)n time and 2n poly(n) space. Our algorithm builds on the lattice point enumer-
ation techniques of Micciancio and Voulgaris (STOC 2010, SICOMP 2013) and Dadush,
Peikert and Vempala (FOCS 2011), and gives an elegant, deterministic alternative to the
“AKS Sieve”-based algorithms for (1 + ε)-CVP (Ajtai, Kumar, and Sivakumar; STOC 2001
and CCC 2002). Furthermore, assuming the existence of a poly(n)-space and 2O(n) -time
algorithm for exact CVP in the `2 norm, the space complexity of our algorithm can be
reduced to polynomial.
Our main technical contribution is a method for “sparsifying” any input lattice while
approximately maintaining its metric structure. To this end, we employ the idea of random
sublattice restrictions, which was first employed by Khot (FOCS 2003, J. Comp. Syst. Sci.
2006) for the purpose of proving hardness for the Shortest Vector Problem (SVP) under ` p
norms.
ACM Classification: F.2.2, F.1.2, G.1.6
AMS Classification: 68W25, 68Q25, 68W20
Key words and phrases: approximation algorithms, high dimensional geometry, lattice algorithms,
closest vector problem
A preliminary version of this paper appeared in the Proc. of the 24th Annual ACM-SIAM Symp. on Discrete Algorithms
(SODA’13).
∗ Research was supported by Subhash Khot’s NSF Waterman Award CCF-1061938, the MTA Rényi “Lendület” Groups and
Graphs Research Group and by the Marie Curie IIF Fellowship Grant No. 627476.
© 2016 Daniel Dadush and Gábor Kun
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2016.v012a002
DANIEL DADUSH AND G ÁBOR K UN
1 Introduction
An n-dimensional lattice L is defined as a set
nn o
∑ zi bi : zi ∈ Z, i ∈ [n]
i=1
for some basis b1 , . . . , bn of Rn . Given a lattice L and norm k · k in Rn , the Shortest Vector Problem
(SVP) is to find a shortest non-zero v ∈ L under k · k. Given an additional target t ∈ Rn , the Closest
Vector Problem (CVP)—the inhomogeneous analog of SVP—is to find a closest v ∈ L to t. Here, one
often works with the `2 norm and other ` p norms, or, most generally, with (possibly asymmetric) norms
induced by a convex body K containing 0 in its interior, defined by
kxkK = inf{s ≥ 0 : x ∈ sK} .
The SVP and CVP on lattices are central algorithmic problems in the geometry of numbers, with
applications to Integer Programming [32], factoring polynomials over the rationals [31], cryptanalysis
(e. g., [42, 25, 41]), and much more. For different applications, one must often consider lattice problems
expressed under a variety of norms. As examples, decoding signals over a Gaussian channel is expressed
as a CVP under `2 [48], computing simultaneous Diophantine approximations is generally expressed as
an SVP under `∞ [18], Schnorr reduced (under some unproven number theoretic assumptions) factoring
to an SVP under the `1 norm [46], the Frobenius problem can be expressed as a lattice problem under an
asymmetric simplicial norm [28], the Integer Programming problem reduces to lattice problems under
near-symmetric norms [27, 12, 11], etc.
Much is known about the computational complexity of SVP and CVP, in both their exact and
approximation versions. On the negative side, SVP in `2 is NP-hard (under randomized reductions)
to solve exactly, or even to approximate to within any constant factor [1, 9, 34, 29]. Many more
hardness results are known for other ` p norms and under stronger complexity assumptions than P 6=
NP [17, 14, 43, 22, 35]. CVP is NP-hard to approximate to within nc/ log log n factors for some constant
c > 0 [4, 15], where n is the dimension of the lattice. Therefore, we do not expect to solve (or even
closely approximate) these problems efficiently in high dimensions. Still, algorithms providing weak
approximations or having super-polynomial running times are the foundations for the many applications
mentioned above.
Though the applications are often expressed using a variety of norms, the majority of the algorithmic
work on SVP and CVP over the last quarter century has focused on the important case of the `2 norm.
While there has been both tremendous practical and theoretical progress for `2 -based solvers, progress
for more general norms has been much slower (we overview this history below). Illustrative of this, for
most of the problems mentioned above, the solution strategy has almost invariably been to approximate
the problem via a reduction to `2 . In many cases, the desired computational problem requires only a
“coarse” approximate solution to the underlying lattice problem (e. g., where a poly(n) or even 2O(n) factor
approximation suffices), in which case approximation by `2 is often sufficient. In some cases, however,
the errors induced by the `2 approximation can result in a substantial increase in worst case running time
or yield unusable results. As an example, with respect to the Integer Programming Problem (IP), in a
sequence of works Dadush, Peikert and Vempala [12, 10] worked directly with norms induced by the
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 2
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
continuous relaxation—avoiding direct ellipsoidal approximations—to reduce the time complexity of
solving an n-variable IP from 2O(n) n2n (the previous best using `2 techniques [24]) to 2O(n) nn . From these
considerations we see that the problem of developing effective algorithms for solving the SVP and CVP
under general norms is well motivated.
The algorithmic history of the SVP and CVP is long and rich. We relate the broad outlines here,
highlighting the pertinent developments for general norms, and refer the reader to [36, 20] for a more
complete accounting. There are three main classes of methods for solving lattice problems: basis
reduction, randomized sieving, and Voronoi cell-based search.
Basis reduction combines both local search on lattice bases and lattice point enumeration. The cele-
brated LLL basis reduction algorithm [31] and further extensions [6, 45] give 2n/polylog(n) approximations
to SVP and CVP under `2 in poly(n) time. Variants of basis reduction for symmetric norms are explored
in [33, 26] and give similar approximation guarantees for SVP (though not for CVP) as the `2 versions.
However, bounds on the time complexity were only proved for fixed dimension (where the running
time is polynomial). For exact SVP and CVP in the `2 norm, Kannan’s algorithm and its subsequent
improvements [27, 23, 21, 38] use basis reduction techniques to deterministically compute solutions in
2O(n log n) time and poly(n) space.
This performance remained essentially unchallenged until the breakthrough randomized “sieving”
algorithm of Ajtai, Kumar and Sivakumar [2], which gave a 2O(n) -time and -space randomized algorithm
for exact SVP under `2 . The randomized sieving approach consists of sampling an exponential number
of “perturbed” lattice points, and then iteratively clustering and combining them to give shorter and
shorter lattice points. Subsequently, the randomized sieve was greatly extended to yield solutions for
more general norms and for (1 + ε)-CVP. For exact SVP, the randomized sieve was extended (in the
same time complexity) to ` p norms [7], symmetric norms [5] and to near-symmetric norms [11]. Here, an
asymmetric norm with unit ball K ⊆ Rn is near-symmetric if voln (K) ≤ 2O(n) voln (K ∩ −K). For CVP,
the randomized sieve was further used to give a (2 + 1/ε)O(n) -time and -space algorithm for (1 + ε)-CVP
under the `2 norm [3, 7], ` p norms [7] and near-symmetric norms [11]. We remark that near-symmetric
norms appear naturally in the context of Integer Programming: the problem of finding a lattice point
near the “center” of the continuous relaxation (which need not be symmetric) can be directly expressed
as a CVP under a near-symmetric norm [11]. Crucially, for any convex body K ⊆ Rn , one can find a
point x ∈ K (e. g., the center of gravity) such that voln ((K − x) ∩ (x − K)) ≥ 2−n voln (K) [39], i. e., such
that K − x is near-symmetric. Lastly, for the specific case of `∞ , Eisenbrand, Hähnle and Niemeier [16]
show that (1 + ε)-CVP can be solved using O(ln(1/ε))n calls to any 2-approximate solver, via an elegant
cube-covering technique. It is worth noting that AKS sieve-based algorithms are Monte Carlo: while
they output correct solutions (i. e., a shortest or closest vector) with high probability, the correctness is
not guaranteed.
In a major breakthrough, Micciancio and Voulgaris [37] gave a deterministic 2O(n) -time and -space
algorithm for exact SVP and CVP under the `2 norm using the Voronoi cell of a lattice. The Voronoi cell,
which is the symmetric polytope consisting of all points in space closer to the origin (under `2 ) than to any
other lattice point, is represented algorithmically here by O(2n ) lattice points corresponding to the facets
of the Voronoi cell (these lattice points are known as Voronoi-relevant vectors). The relevant vectors form
an “extended basis” for the lattice, which Micciancio and Voulgaris (MV) use to efficiently guide closest
lattice point search. Though it is tempting to try and directly extend the MV techniques to other norms,
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 3
DANIEL DADUSH AND G ÁBOR K UN
this appears to be quite challenging. A major difficulty is that for more general norms the Voronoi cell
need not be convex, and furthermore, no good bounds are known for the number of relevant vectors. In
a subsequent work, however, Dadush, Peikert and Vempala [12] showed that MV lattice point search
techniques can, in a qualified sense, be extended to general norms (in fact, to general convex bodies)
by reducing lattice problems to enumeration within ellipsoids. Combining a technique for constructing
“efficient” ellipsoid coverings—using the M-Ellipsoid concept from convex geometry—together with
Voronoi cell-based search, they showed that the lattice points inside a convex body can be computed in
time proportional to the maximum number of lattice points that any translation of the body can contain.
With some further improvements [13, 10], the DPV lattice point enumeration technique was used to
give the first deterministic 2O(n) -time and -space algorithms for SVP and α-Bounded Distance Decoding
(α-BDD), for any fixed constant α > 0, under near-symmetric norms.1
Given the recent progress for general norm lattice problems, a major open problem is whether there
exists a 2O(n) -time algorithm for solving exact CVP under near-symmetric norms (which would also
imply a 2O(n) -time algorithm for Integer Programming [11]). While this problem seems currently out of
reach, a natural next question is whether one can improve the extant (1 + ε)-approximation algorithms
for near-symmetric norm CVP. In particular, does there exist a deterministic algorithm for (1 + ε)-CVP
achieving comparable asymptotic complexity to the randomized sieving algorithms?
1.1 Results and techniques
Building on the DPV lattice point enumeration techniques, we give the first deterministic algorithm for
(1 + ε)-CVP with comparable asymptotic complexity to the AKS randomized sieve. Our main theorem is
stated as follows:
Theorem 1.1 (Approximate CVP in any norm, informal). There is a deterministic algorithm that, given
any near-symmetric norm k · kK , n-dimensional lattice L, target x ∈ Rn and 0 < ε ≤ 1, computes y ∈ L,
a (1 + ε)-approximate minimizer of ky − xkK in (1 + 1/ε)n · 2O(n) time and Õ(2n ) space.
Compared to AKS, our approach also achieves a better dependence on ε, namely, 2O(n) (1 + 1/ε)n
instead of 2O(n) (1 + 1/ε)2n , and uses significantly less space, namely, Õ(2n ) compared to 2O(n) (1 + 1/ε)n .
Additionally, as we will discuss below, continued progress for exact CVP under `2 could further reduce
the space usage of the algorithm. We note, however, that the 2O(n) factor in the running time is currently
much larger than in AKS, though little effort has been spent in trying to calculate or optimize it. To explain
our approach, we first present the main DPV enumeration algorithm in its most recent formulation [10].
Theorem 1.2 (Enumeration in Convex Bodies, informal). There is a deterministic algorithm that, given
an n-dimensional bounded convex body K and an n-dimensional lattice L, enumerates the elements of
K ∩ L in time 2O(n) G(K, L) using Õ(2n ) space, where G(K, L) = maxx∈Rn |(K + x) ∩ L|. Furthermore,
given an algorithm that solves exact CVP on n-dimensional lattices under `2 in T (n) time and S(n) space,
K ∩ L can be enumerated in 2O(n) T (n)G(K, L) time using S(n) + poly(n) space.
1 α-BDD is the promise version of CVP where the distance to the target is guaranteed to be at most an α-factor times the
length of the shortest non-zero vector of the lattice.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 4
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
The above lattice point enumerator will form the core of our (1 + ε)-CVP algorithm. As we will show,
the space used by our approximate CVP algorithm will only be larger than that used for the enumeration
algorithm by an additive polynomial term. Therefore, if one could develop an algorithm for exact CVP
under `2 which runs in 2O(n) time and poly(n) space, then the space usage of our (1 + ε)-CVP algorithm
would be reduced to poly(n) in the same time complexity. The possibility of such a solver is discussed
in [37], and devising one remains an important open problem. We remark that by plugging in Kannan’s
algorithm for CVP under `2 , we do indeed get a poly(n)-space (1 + ε)-CVP solver, though at the cost of
an nn/2 factor increase in running time.
Using the above enumerator as a black box, we now present the approach taken in [12] to solve CVP
and explain the main problem that arises. Given the target t ∈ Rn , the algorithm first computes an initial
coarse underestimate d0 of the distance of t to L under k · kK (using LLL, for example). For the next step,
they use the lattice point enumerator to successively compute the sets (t + 2i d0 K) ∩ L (i. e., all lattice
points at distance at most 2i d0 from t), i = 0, 1, 2, . . . , until a lattice point is found. Finally, a closest
vector to t in the final enumerated set is returned.
From the description, it is relatively straightforward to show that the complexity of the algorithm is
essentially G(dK, L), where d is the distance of t to L. The main problem with this approach is that,
in general, one cannot a priori bound G(dK, L); even in 2 dimensions and for the Euclidean norm this
quantity can be arbitrarily large. The only generic setting where such a bound is indeed available is when
the distance d of the target is bounded by αλ , where λ is the length of a shortest non-zero lattice vector
under k · kK . In this situation, we can bound G(dK, L) by 2O(n) (1 + α)n . We note that this bound depends
crucially on K being near-symmetric, that is, one can construct examples where G(dK, L) is arbitrarily
large when K has no near-symmetry requirement. We remark further that solving CVP with this type of
guarantee corresponds to α-BDD, and by a standard reduction it can be used to solve SVP (using α = 1
above) in near-symmetric norms as well [19].
To circumvent the above problem, we propose the following simple solution. Instead of solving the
CVP on the original lattice L, we attempt to solve it on a sparser sublattice L0 ⊆ L, where the distance of
t to L0 is not much larger than its distance to L (we settle for an approximate solution here) and where
the maximum number of lattice points at the new target distance is appropriately bounded. Our main
technical contribution is to show the existence of such “lattice sparsifiers,” and to give a deterministic
algorithm to compute them:
Theorem 1.3 (Lattice Sparsifier, informal). There is a deterministic algorithm that, given any n-
dimensional lattice L, any near-symmetric norm k · kK , and distance t ≥ 0, computes a sublattice
L0 ⊆ L in 2O(n) time and Õ(2n ) space satisfying: (1) the distance from any point in Rn to L0 is at most t
plus its distance to L, (2) the number of points in L0 at distance t from any point in Rn is at most 2O(n) .
We shall call a sublattice L0 ⊆ L satisfying the conditions of Theorem 1.3 a (K,t)-sparsifier for L, or
simply a t-sparsifier for L when the context is clear.
Given such sparsifiers, efficiently solving (1 + ε)-CVP is straightforward. We simply compute a
sparsifier L0 for L under k · kK with t = εdK (t, L) (the distance from t to L), and then solve the exact
CVP on L0 using the DPV algorithm. By the guarantees on the sparsifier, L0 contains a point at distance
at most dK (t, L) + εdK (t, L) = (1 + ε)dK (t, L), and using a simple packing argument (see Lemma 2.3)
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 5
DANIEL DADUSH AND G ÁBOR K UN
we can show that
1 n 1 n
G((1 + ε)dK, L0 ) = 2O(n) 1 + G(εdK, L0 ) = 2O(n) 1 + .
ε ε
Here we note that the correctness of the output follows from the distance-preserving properties of L0 , and
the desired running time follows from the above bound on G((1 + ε)dK, L0 ).
Apart from enabling a deterministic algorithm, we believe that the use of lattice sparsifiers makes
the mechanics of our algorithm far more transparent than the randomized sieving approaches. Indeed, it
was in trying to understand why the randomized sieving methods work that we were led to the sparsifier
concept.
Another benefit of our construction is that it helps elucidate an important qualitative difference
between approximate and exact CVP under near-symmetric norms. In particular, our construction shows
that one can often retain only a small fraction of the lattice without changing the distance to the target by
much, while almost surely losing the exact closest vector. We note that it was shown in [11] that there
is a randomized polynomial-time reduction from integer programming feasibility (deciding whether a
convex body contains an integer point) to exact CVP under near-symmetric norms, and the current fastest
integer programming algorithms have complexity nO(n) [27, 10].
Existence of sparsifiers. We note that it is far from obvious that lattice sparsifiers, as described in
Theorem 1.3, even exist. Somewhat surprisingly, these good sparsifying sublattices are ubiquitous: one
can show that a random sublattice of L chosen from a certain uniparametric family satisfies the conditions
of Theorem 1.3 with lower bounded constant probability. Interestingly, this same family of random
sublattices was used by Khot [30, 29] as a tool for creating hard SVP instances (in fact, he uses them to
perform a “very weak” version of sparsification).
Let us assume that K ⊆ Rn is a symmetric convex body (the near symmetric case reduces to this
by taking K ∩ −K). To show the existence of sparsifiers for L and K, we shall essentially reduce to the
following task: for any t > 0, find a sublattice L0 ⊆ L such that
1. the shortest non-zero vector of L0 with respect to k · kK has length ≥ t,
2. every element of L is at distance at most αt from L0 , for some absolute constant α ≥ 1.
Let us now show that both these conditions imply that L0 is a distance αt-sparsifier for L.
Firstly, by the packing bound (see Lemma 2.3 part 1) and condition (1), the number of vectors in L0
at distance αt from any point is G(αtK, L) ≤ (1 + 2α)n = 2O(n) .
Secondly, condition (2) ensures that for any vector t in Rn , the distance from L0 is at most an additive
αt more than its distance to L. To see this, let x be a closest vector to t in L, and let y be a closest vector
to x in L0 . By the triangle inequality,
ky − tkK ≤ ky − xkK + kx − tkK ≤ αt + kx − tkK ,
as claimed. Hence L0 is a valid distance αt-sparsifier for L.
We now outline two methods to construct L0 , beginning with a natural approach based on scaling a
good basis, which presents difficulties, and a second approach based on random sublattices, which forms
the heart of our algorithm.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 6
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Basis scaling. A first natural approach for building L0 is to start with a “short” basis b1 , . . . , bn of L,
and let L0 be generated by a suitable integer scaling of the basis vectors. Here we would like to integrally
scale up the basis vectors (with a potentially different scaling for each basis element) as little as possible
so as to ensure that L0 contains no non-zero vectors of length at most t.
Unfortunately, it is not easy to accurately lower bound the length of the shortest vector of L0 just
by looking at one of its bases. The most useful lower bound on the length here, under the Euclidean
norm, is the minimum norm of the Gram-Schmidt orthogonalization of the basis (which has a natural
generalization to other norms). This value, however, can be much smaller than the minimum norm
of the non-orthogonalized basis. In particular, if one integrally scales the starting basis so that all the
Gram-Schmidt vectors have length at least t, then even starting from the “best” basis (say Hermite-
Korkine-Zolotareff or Seysen reduced [47]), standard techniques only allow us to show a bound of
nO(log n)t on the distance of L to L0 , which is far too large for our application. We remark that even
when L has an orthogonal basis and the norm is Euclidean, scaling the orthogonal basis can lead to L
√
having points at distance Ω( nt) from L0 .
Random sublattices. We now present the approach taken throughout the rest of the paper. For simplic-
ity of presentation (and without loss of generality), we shall assume that L = Zn . We recall that every
full-rank sublattice L0 of Zn can be expressed as
L0 = {x ∈ Zn : Ax ≡ 0 (mod mZk )}
where A is a k × n matrix, k ≤ n, with entries in Zm (integers mod m), for some k, m ∈ N. That is, every
sublattice of Zn is the solution set to a homogeneous system of modular equations. In a precise sense,
finding a good sparsifying matrix A is in fact “dual” to the basis scaling approach.
To show that we can find an αt-sparsifier L0 , it will be helpful to rephrase conditions (1) and (2) in
terms of the matrix A. Let GA = {Ax (mod mZk ) : x ∈ Zn }. Note that GA is an abelian group of size at
most mk and that L (mod L0 ) is isomorphic to GA . In all cases of interest, the image of A will be Zkm , in
which case GA ' Zkm . For L0 to be our desired sparsifier, we want A ∈ Zk×nm such that:
1’. For all x ∈ Zn \ {0}, kxkK ≤ t, Ax 6≡ 0 (mod mZk ).
2’. For all c ∈ GA , there exists x ∈ Zn , kxkK ≤ αt, such that c ≡ Ax (mod mZk ).
As mentioned previously, our choice for A will be random. At a high level, we will want a distribution
over A for which the values Ax (mod mZk ), x ∈ tK ∩ Zn , are “well spread.” The most natural such
distribution is to let the coefficients of A be chosen uniformly from Zm . With this choice, for any vector
x ∈ Zn containing at least one coefficient relatively prime to m, the random vector Ax (mod mZk ) is
uniform in Zkm . Hence, we should expect the map hA (x) = Ax (mod mZk ) to act like a good hash function.
With this in mind, we now outline why we can choose k and m so that conditions (10 ) and (20 ) are satisfied
with constant probability.
Condition 1’. From the perspective of condition (10 ), if the non-zero points in tK ∩ Zn are “generic
enough” (i. e., having some coefficients relatively prime to m), then each of them gets mapped to 0 under
hA with probability m−k . Therefore, as long as mk (the size of the group Zkm ) is a constant factor larger
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 7
DANIEL DADUSH AND G ÁBOR K UN
than |tK ∩ Zn |, by the union bound a random choice of A should ensure that L0 contains no non-zero
vectors of length ≤ t with constant probability.
To satisfy the genericity assumption, it suffices to pick m to be a prime p ≥ |tK ∩ Zn |. To see this,
note that if a non-zero x ∈ tK ∩ Zn does not have a relatively prime coefficients to p, then x/p ∈ Zn and
by convexity kx/p ∈ tK ∩ Zn for 0 ≤ k ≤ p (since 0 ∈ K). But then |tK ∩ Zn | ≥ p + 1, a contradiction.
From here, since the probability of hitting 0 only depends on the size mk , we may as well set k = 1 (we
will see another reason for this later), letting A contain a single row.
Our choice of m, k is now reduced to choosing a suitable prime p ≥ |tK ∩ Zn |. We replace the matrix A
with a vector a chosen uniformly from Znp , and we let ha (x) = ha, xi (mod p).
Condition 2’. We now explain why condition (20 ) can be made to hold simultaneously with (10 ).
We recall our current choice of k = 1 and m = p with p prime. With this choice, A is now a uniformly
chosen vector a ∈ Znp . For each z ∈ Z p , we associate the coset L0z = {x ∈ Zn : ha (x) ≡ z (mod p)} of L0 ,
and define the length of L0z to be min{kxkK : x ∈ L0z }. Note that L/L0 = {L0z : z ∈ Z p } as long as a 6= 0.
With this notation, our task is now to show that with constant probability, for a random a ∈ Znp , every
coset L0z , z ∈ Z p , has length at most αt, for α = O(1).
Note that if the size of the group Z p is much larger than |tK ∩ L|, then there may not be enough
elements in αtK ∩ Zn for this to be possible. On the other hand, if |Z p | < |tK ∩ L|, then we guarantee
the existence of short vectors in L0 (of length at most 2t) by the pigeonhole principle. Hence, for our
construction to work it makes sense to choose p = r|tK ∩ Zn | for some 1 < r = O(1).
We note that by construction, the cosets of L0 induced by R = {ha (x) : x ∈ tK ∩ Zn } have length at
most t. The crucial observation is that if the cosets induced by R are short, then so are the cosets induced
by R + R = {a + b : a, b ∈ R}, since by the triangle inequality they have length at most 2t (this is the last
place the convexity of K is needed). Hence we can hope to show that if |R| is large with respect to p,
then we can cover all of Z p with a constant number of sums of R, which would imply that all cosets
L0z , z ∈ Z p , have length O(t). Of course, if R was already a subgroup of Z p , then this process could not
succeed. Crucially, Z p has no non-trivial proper subgroups—this is the main reason to chose k = 1 and m
prime—and hence this obstruction is avoided.
At this point, we rely on the well-known Cauchy-Davenport sumset inequality in additive combi-
natorics, which states for any subsets C, D ⊆ Z p that |C + D| ≥ min{p, |C| + |D| − 1}. Since sumsets
in Z p grow at least linearly fast, given the previous observations, it suffices to show that |R| = Ω(p)
with constant probability. Since R = ha (tK ∩ Zn ) and p is chosen to be Θ(|tK ∩ Zn |), we simply need to
show that a random ha is close to being injective on tK ∩ Zn . This will follow from the fact that ha is a
good hash function. In particular, the probability that distinct elements x, y ∈ Znp collide under ha (that is
ha (x) = ha (y)) is exactly 1/p. Using a slight strengthening of the genericity argument for condition (10 ),
one can show that points in tK ∩ Zn are in fact all distinct when taken mod pZn . Assuming this over
all pairs of points in tK ∩ Zn the expected number of collisions is roughly O(|tK ∩ Zn |2 /p) = O(p).
Therefore the average element in tK ∩ Zn collides with O(p/|tK ∩ Zn |) = O(1) other elements. From
this, one can easily deduce that the map ha can only shrink tK ∩ Zn by a constant factor, as needed. This
completes the description of our randomized construction.
Derandomizing the construction. We claim in Theorem 1.3 to give a deterministic 2O(n) -time con-
struction for lattice sparsifiers, whereas the above construction is clearly randomized.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 8
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
To make the construction completely deterministic, we rely on the following main ideas. Firstly,
instead of computing the sparsifier in one step, we compute a sequence of sparsifiers
L = L0 ⊇ L1 ⊇ · · · ⊇ Lk ,
with a geometric sparsification rate. This allows us to maintain that the sparsification distance at each
step is (roughly speaking) at most a constant factor larger than the minimum distance (length of shortest
non-zero vector) of the working lattice, and hence the number of lattice points the next sparsifier needs to
remove at each step is bounded by 2O(n) .
Second, given a sparsification set tK ∩ Zn (we take any basis of Li to rephrase the problem in terms
of Zn ) of size 2O(n) as above, we need to find the sparsifying vector a ∈ Znp , for p = Θ(|tK ∩ Zn |), quickly
2
and deterministically. Here, naive exhaustive search requires at least pn = 2O(n ) time, since a has n
coordinates. Instead, we show that one can, roughly speaking, choose the coordinates of a one at a time
(not in a fixed basis however) in pO(1) time, requiring npO(1) time for the whole vector.
We defer a detailed outline of our deterministic construction to Section 5.
Organization. In Section 3, we provide the exact reduction from (1 + ε)-CVP to lattice sparsification,
formalizing Theorem 1.1. In Section 4, we prove the existence of lattice sparsifiers using the probabilistic
method. In Section 5, we give the derandomized lattice sparsifier construction, formalizing Theorem 1.3.
Lastly, in Section 6, we discuss further applications and future directions.
2 Preliminaries
Convexity and norms. For sets A, B ⊆ Rn , let A + B = {a + b : a ∈ A, b ∈ B} denote their Minkowski
sum. Bn2 denotes the n-dimensional Euclidean unit ball in Rn . A convex body K ⊆ Rn is a full-dimensional
compact convex set. A convex body K is (a0 , r, R)-centered if a0 + rBn2 ⊆ K ⊆ a0 + RBn2 . For a convex
body K ⊆ Rn containing 0 in its interior, we define the (possibly asymmetric) norm k · kK induced by K
as kxkK = inf{s ≥ 0 : x ∈ sK}. For a (0, r, R)-centered convex body K, we note that
1 1
kxk2 ≤ kxkK ≤ kxk2 .
R r
If K is symmetric (i. e., K = −K), then k · kK is also symmetric (kxkK = k − xkK ). A convex body K
is γ-symmetric for γ ∈ (0, 1] if voln (K ∩ −K) ≥ γ n voln (K). We say that K is near-symmetric if it is
Ω(1)-symmetric.
Computational model. The convex bodies and norms will be presented to our algorithms via weak
membership and distance oracles. For ε ≥ 0 and a convex body K ⊆ Rn , we define K ε = K + εBn2 and
K −ε = {x ∈ K : x + εBn2 ⊆ K}. A weak membership oracle OK for K is a function which takes as input
a point x ∈ Qn and rational ε > 0, and returns OK (x, ε) = 1 if x ∈ K −ε , 0 if x ∈
/ K ε , and either 0 or 1 if
−ε
x ∈ K \ K . A weak distance oracle DK,· for K is a function that takes as input a point x ∈ Qn and
ε
rational ε > 0, and returns a rational number DK,ε (x) satisfying |DK,ε (x) − kxkK | ≤ ε min{1, kxkK }. All
our oracles will come with a guarantee that their associated convex body K is (a0 , r, R)-centered, for some
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 9
DANIEL DADUSH AND G ÁBOR K UN
a0 ∈ Qn and rational 0 < r ≤ R. The running time of our algorithms will be measured by the number of
oracle calls and arithmetic operations, where we shall consider the bit description length of the oracle
guarantees as part of the input. It is not hard to check that given centering guarantees a weak membership
and distance oracle for K are polynomial time equivalent, hence we shall assume that we can convert
between the two at no essential cost. For simplicity, we use the notation poly(·) to denote a polynomial
factor in all the relevant input parameters (dimension, encoding length of basis / oracle guarantees, etc.).
In this paper, all arithmetic operations will occur on numbers of size polynomial in the input length.
Lattices. A full rank n-dimensional lattice L ⊂ Rn is a full-dimensional discrete subgroup of Rn . We
will consider lattices of full rank in this paper. Equivalently, L can be expressed as BZn , where B ∈ Rn×n
is a non-singular matrix, which we refer to as a basis for L. The dual lattice of L is
L∗ = {y ∈ Rn : ∀x ∈ L, hx, yi ∈ Z} ,
which is generated by the basis B−T (the inverse transpose of B). For a sublattice M ⊆ L, we define the
quotient group L/M = {M + a : a ∈ L}, corresponding to the cosets of L modulo M. We shall use the
shorthand Znp = Zn /pZn , for a natural number p ∈ N.
We define the length of the shortest non-zero vector (minimum distance) of L under k · kK by
λ1 (K, L) = min kykK .
y∈L\{0}
We let
SVP(K, L) = arg minz∈L\{0} kzkK
denote the set of shortest non-zero vectors of L under k · k. For x ∈ Rn , define the distance of x to L
under k · kK by
dK (L, x) = min ky − xkK .
y∈L
We let
CVP(K, L, x) = arg miny∈L ky − xkK
denote the set of closest vectors to x in L under k · kK .
Covering numbers and lattice point bounds. For a set A ⊆ Rn , let int(A) denote the interior of A.
For convex bodies A, B ⊆ Rn , we define the covering number
N(A, B) = inf{|Λ| : Λ ⊆ Rn , A ⊆ Λ + B} ,
i. e., the minimum number of translates of B needed to cover A. We will require the following standard
inequalities on the covering numbers. We include proofs for completeness.
Lemma 2.1. Let A, B ⊆ Rn be convex bodies, where B is symmetric. Then
voln (A + B/2)
N(A, B) ≤ .
voln (B/2)
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 10
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Proof. Let T ⊆ A be any maximal set of points such that for all distinct x, y ∈ T , (x+B/2)∩(y+B/2) = 0.
/
We claim that A ⊆ T + B. Note that by the maximality of T for any z ∈ A there exists x ∈ T such that
(z + B/2) ∩ (x + B/2) 6= 0.
/ Therefore z ∈ x + B/2 − B/2 = x + B, as needed.
Since T + B/2 corresponds to |T | disjoint translates of B/2, we have that
|T | voln (B/2) = voln (T + B/2) ≤ voln (A + B/2) .
Rearranging the above inequality yields the lemma.
Lemma 2.2. For any convex body K ⊆ Rn and d > 0, we have N(dK, K) ≤ (4d + 2)n .
Proof. From the well-known relation
Z Z Z
voln ((K − x) ∩ (x − K))/ voln (K) dx = 1[2x − y ∈ K]/ voln (K) dy dx
K ZK K
= voln ((K + y)/2)/ voln (K) dy = 2−n ,
K
there exists x ∈ K such that K[x] = (K − x) ∩ (x − K) satisfies voln (K[x])/ voln (K) ≥ 2−n .
By Lemma 2.1, since K[x] is symmetric, we have
voln (dK + K[x]/2)
N(dK, K) ≤ N(dK, K[x]) ≤
voln (K[x]/2)
voln ((d + 1/2)K) voln (K)
≤ = (2d + 1)n ≤ (4d + 2)n ,
voln (K[x]/2) voln (K[x])
as needed.
For a lattice L and a convex body K in Rn , let G(K, L) be the largest number of lattice points
contained in any translate of K, that is
G(K, L) = maxn |(K + x) ∩ L| .
x∈R
We will need the following bounds on G(K, L) from [10]. We include a proof for completeness.
Lemma 2.3. Let K ⊆ Rn denote a γ-symmetric convex body and let L denote an n-dimensional lattice.
Then for d > 0 we have that
n
−n 2d
1. G(dK, L) ≤ γ 1+ ,
λ1 (K ∩ −K, L)
2. G(dK, L) ≤ γ −n (2d + 1)n · |(K ∩ −K) ∩ L| ,
3. G(dK, L) ≤ N(dK, K)G(K, L) ≤ (4d + 2)n G(K, L).
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 11
DANIEL DADUSH AND G ÁBOR K UN
Proof of 1. Let s = (1/2)λ1 (K ∩ −K, L). For x ∈ L, we examine
x + int(s(K ∩ −K)) = {z ∈ Rn : kz − xkK∩−K < s} .
Now for x, y ∈ L, x 6= y, we claim that
(x + int(s(K ∩ −K))) ∩ (y + int(s(K ∩ −K))) = 0/ . (2.1)
Assume not, then there exists z ∈ Rn such that kz − xkK∩−K , kz − ykK∩−K < s. Since K ∩−K is symmetric,
we note that ky − zkK∩−K = kz − ykK∩−K < s. But then we have that
ky − xkK∩−K = ky − z + z − xkK∩−K ≤ ky − zkK∩−K + kz − xkK∩−K
< s + s = 2s = λ1 (K ∩ −K, L) ,
a clear contradiction since y − x 6= 0.
Take c ∈ Rn . To bound G(dK, L) we must bound |(c + dK) ∩ L|. For x ∈ c + dK, we note that
x + s(K ∩ −K) ⊆ c + (d + s)K. Therefore,
voln ((d + s)K) = voln (c + (d + s)K) ≥ voln (((c + dK) ∩ L) + s(K ∩ −K))
= |(c + dK) ∩ L| voln (s(K ∩ −K))
where the last equality follows from (2.1). Therefore, we have that
d +s n
n
voln ((d + s)K) −n 2d
|(c + dK) ∩ L| ≤ = =γ 1+ ,
voln (s(K ∩ −K)) γs λ1 (K ∩ −K, L)
as needed.
Proof of 2. Examine dK + c. Let y1 , . . . , yN ∈ (dK + c) ∩ L denote a maximal collection of points such
that the translates
1
yi + (K ∩ −K) , i ∈ [N] ,
2
are interior disjoint. We claim that
N
(dK + c) ∩ L ⊆
[
yi + (K ∩ −K) .
i=1
Take z ∈ (dK + c) ∩ L. Then by the construction of y1 , . . . , yN , there exists i ∈ [N] such that
1 1
z + (K ∩ −K) ∩ yi + (K ∩ −K) 6= 0/ ,
2 2
which implies that z ∈ yi + (K ∩ −K), as needed. Therefore
n
|(dK + c) ∩ L| ≤ ∑ |(yi + (K ∩ −K)) ∩ L| = N|(K ∩ −K) ∩ L| .
i=1
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 12
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Since K is γ-symmetric, we get that
Sn 1 1
voln ( i=1 yi + 2 (K ∩ −K)) n −n voln (dK + 2 (K ∩ −K))
N= 1
≤ 2 γ ≤ γ −n (2d + 1)n ,
voln ( 2 (K ∩ −K)) voln (K)
as needed. Since the above bound holds for all c ∈ Rn , we get that
G(dK, L) ≤ γ −n (2d + 1)n · |(K ∩ −K) ∩ L| ,
as needed.
Proof of 3. Choose T ⊆ Rn such that dK ⊆ T + K and |T | = N(dK, K). Then for any c ∈ Rn ,
|(dK + c) ∩ L| ≤ |(K + T + c) ∩ L| ≤ ∑ |(K + y + c) ∩ L| ≤ |T | max |(K + y + c) ∩ L|
y∈T y∈T
≤ N(dK, K)G(K, L) ≤ (4d + 2)n G(K, L) ,
as needed.
Algorithms. We will need the following lattice point enumeration algorithm from [12, 10].
Theorem 2.4 (Algorithm Lattice-Enum(K, L, ε)). Let K ⊆ Rn be a (a0 , r, R)-centered convex body given
by weak membership oracle OK , let L ⊆ Rn be an n-dimensional lattice with basis B ∈ Qn×n and let
ε > 0. Then there is a deterministic algorithm that on inputs K, L, ε (lazily) outputs a set S satisfying
K ∩ L ⊆ S ⊆ (K + εBn2 ) ∩ L
in G(K, L) · 2O(n) · poly(·) time using 2n poly(·) space.
We will require the following SVP solver from [12, 10].
Theorem 2.5 (Algorithm Shortest-Vectors(K, L, ε)). Let K ⊆ Rn be a (a0 , r, R)-centered symmetric
convex body given by a weak membership oracle OK , and let L ⊆ Rn be an n-dimensional lattice with
basis B ∈ Qn×n , and let ε > 0. Let λ1 = λ1 (K, L). Then there is an algorithm that on inputs K, L, ε
outputs a set S ⊆ L satisfying
SVP(K, L) ⊆ S ⊆ {y ∈ L \ {0} : kykK ≤ λ1 + ε min{1, λ1 }} (2.2)
in deterministic 2O(n) poly(·) time and 2n poly(·) space.
3 CVP via lattice sparsification
To start, we give a precise definition of a lattice sparsifier.
Definition 3.1 (Lattice Sparsifier). Let K ⊆ Rn be a γ-symmetric convex body, L be an n-dimensional
lattice and t ≥ 0. A (K,t)-sparsifier for L is a sublattice L0 ⊆ L satisfying
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 13
DANIEL DADUSH AND G ÁBOR K UN
1. G(tK, L0 ) = γ −n 2O(n) ,
2. ∀x ∈ Rn , dK (L0 , x) ≤ dK (L, x) + t.
For the above, we trivially have dK (L0 , x) ≥ dK (L, x), and hence L0 preserves distances up to additive
error t. For t < λ1 (K − K, L), it is relatively straightforward to check that G(tK, L) = 1, and hence L is a
(K,t)-sparsifier for itself. The above definition therefore only becomes interesting above t > λ1 (K − K, L).
Indeed, the sparsification distances used in our algorithms may be arbitrarily larger than this in general.
We now prove a simple equivalence between building a sparsifier for symmetric and asymmetric
norms. This will be useful for our sparsifier construction.
Lemma 3.2. Let K be a γ-symmetric convex body, L be an n-dimensional lattice, L0 ⊆ L be an n-
dimensional sublattice and t > 0. If L0 is a (K ∩ −K,t)-sparsifier for L then it is also a (K,t)-sparsifier
for L.
Proof. Let L0 ⊆ L be a (K ∩ −K,t)-sparsifier. Since K ∩ −K is 1-symmetric, we have by definition that
G(t(K ∩ −K), L0 ) = 2O(n) . By Lemma 2.1 and γ-symmetry of K, we have that
voln (K + 21 (K ∩ −K)) voln ( 32 K)
N(tK,t(K ∩ −K)) = N(K, K ∩ −K) ≤ ≤ ≤ 3n γ −n .
voln ( 12 (K ∩ −K) voln ( 21 (K ∩ −K))
Therefore
G(tK, L0 ) ≤ N(tK,t(K ∩ −K))G(t(K ∩ −K), L0 ) = (3n γ −n )2O(n) = γ −n 2O(n) ,
as needed. Since K ∩ −K ⊆ K, we note that kakK ≤ kakK∩−K for all a ∈ Rn . Take x ∈ Rn and z ∈
CVP(K, L, x). By the guarantee on L0 , there exists y ∈ L0 such that
ky − zkK∩−K ≤ dK∩−K (L, z) + t = t ,
where the last equality follows since z ∈ L. Using the triangle inequality, we have that
ky − xkK ≤ ky − zkK + kz − xkK ≤ ky − zkK∩−K + dK (L, x) ≤ dK (L, x) + t ,
as needed. Therefore, L0 is a (K,t)-sparsifier for L as claimed.
The following theorem represents the formalization of our lattice sparsifier construction.
Theorem 3.3 (Algorithm Lattice-Sparsifier). Let K ⊆ Rn be a (0, r, R)-centered and γ-symmetric convex
body specified by a weak membership oracle OK , and let L denote an n-dimensional lattice given by basis
B ∈ Qn×n . For t ≥ 0, a basis B0 ∈ Qn×n for a (K,t)-sparsifier L0 for L can be computed in deterministic
2O(n) poly(·) time and 2n poly(·) space.
The proof of the above theorem is the subject of Sections 4 and 5 (which give randomized and
deterministic constructions, respectively). Using the above lattice sparsifier construction, we present the
following simple algorithm (Algorithm 1) for (1 + ε)-CVP, which formalizes the algorithm presented in
the introduction.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 14
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
We now sketch Algorithm 1 and its analysis, avoiding the technical details associated with distance
oracles. To begin, the algorithm computes a lower bound d on dK (L, x). It then successively doubles d
until x + (1 + ε/3)dK intersects an (ε/3)d-sparsifier L0 for L, which we check via enumeration. At this
point, we return all closest vectors to x in L0 using enumeration.
For the running time, every enumeration takes at most 2O(n) (1/ε)n γ −n time since we only enumerate
on appropriately sparsified lattices. Furthermore, it is clear that the enumeration at the last phase controls
the complexity of algorithm. For the approximation guarantee, we first note that if d ≥ dK (L, x) the
(ε/3)d-sparsifier L0 contains a lattice vector at distance (1 + ε/3)d from x, and hence the algorithm
returns all closest vectors to x in L0 . In particular, we see that at the final iteration d/2 ≤ dK (L, x), since
otherwise we would have terminated in the previous iteration. Thus at the final iteration, L0 in fact
contains a vector at distance dK (L, x) + εd/3 < (1 + ε)dK (L, x) from x, as needed.
Algorithm 1 Approx-Closest-Vectors(K, L, x, ε)
Require: (0, r, R)-centered convex body K ⊆ Rn with weak distance oracle DK for k·kK , a basis B ∈ Qn×n
for L, target x ∈ Qn , 0 < ε ≤ 1.
Ensure: a non-empty set S ⊆ {y ∈ L : ky − xkK ≤ (1 + ε)dK (L, x)}.
1: if x ∈ L then return {x}
2: Compute z ∈ CVP(Bn2 , L, x) using the MV algorithm.
3: l ← kz − xk2 /R; ε0 ← (ε/9) min{1, l}.
4: d ← l/2; d˜x ← ∞.
5: repeat
6: d ← 2d.
7: L0 ← Lattice-Sparsifier(K, L, ε3 d).
8: for all y ∈ Lattice-Enum((1 + ε3 )dK + x, L0 , rε0 ) do
9: d˜x ← min{d˜x , DK,ε0 (y − x), (1 + ε3 )d + ε0 }.
10: until d˜x < ∞
11: return Lattice-Enum((d˜x + ε0 )K + x, L0 , rε0 )
Theorem 3.4. Algorithm 1 (Approx-Closest-Vectors) is correct, and on inputs K, L, x, ε (as above), where
K is γ-symmetric, it runs in deterministic 2O(n) γ −n (1 + 1/ε)n poly(·) time and 2n poly(·) space.
Proof. We separately establish correctness and running time.
Correctness: If x ∈ L then we are clearly done. Next, since K is (0, r, R)-centered, we have that
kyk2 kyk2
≤ kykK ≤
R r
for all y ∈ Rn . Now take any z̃ ∈ CVP(K, L, x) and z ∈ CVP(Bn2 , L, x) (as in the algorithm). Define
dx = kz̃ − xkK , where we note that dx = dK (L, x). As in the algorithm, let l = kz − xk2 /R. Now we see
that
kz − xk2 kz̃ − xk2 kz − xk2 R
l= ≤ ≤ kz̃ − xkK = dx ≤ kz − xkK ≤ =l .
R R r r
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 15
DANIEL DADUSH AND G ÁBOR K UN
Therefore, l ≤ dx ≤ lR/r.
Let d f denote the value of d after the repeat loop terminates. We claim that
1 ε
d f ≤ dx ≤ 1 + d f + ε0 .
2 3
When the repeat loop terminates, we are guaranteed that the call to
ε
Lattice-Enum 1 + d f K + x, L0 , rε0
3
outputs a lattice vector in L0 at distance at most (1 + ε/3)d f + ε0 from x under k · kK . Since L0 ⊆ L, we
clearly have that dx ≤ (1 + ε/3)d f + ε0 as needed.
If the repeat loop terminates after the first iteration, then d f = l ≤ dx and hence (1/2)d f < dx , as
needed. If the loop iterates more than once, then for the sake of contradiction, assume that (1/2)d f > dx .
Then in the before last iteration, the value of d is greater than dx . Now we are guaranteed that Lattice-
Sparsifier(K, L, (ε/3)d) returns a lattice L0 satisfying
ε ε
dK (L0 , x) ≤ dK (L, x) + d ≤ 1 + d.
3 3
But then the call to ε
Lattice-Enum 1+ dK + x, L0 , rε0
3
is guaranteed to return a lattice point, and hence the repeat loop terminates at this iteration, a clear
contradiction. Hence (1/2)d f ≤ dx , as needed.
Let dx0 = dK (L0 , x), for L0 at the end of the repeat loop. We now claim that d˜x (as in the algorithm)
satisfies dx0 − ε0 ≤ d˜x ≤ dx0 + ε0 . We first note that d˜x = min{(1 + ε/3)d f + ε0 , DK,ε0 (z − x)} for some
z ∈ L0 . By the guarantees on DK,ε0 (·) and Lattice-Enum, we get that
d˜x = min{(1 + ε/3)d f + ε0 , DK,ε0 (z − x)} ≥ min{dx0 , kz − xkK − ε0 } ≥ dx0 − ε0 ,
as needed. For the second inequality, we examine two cases. First assume that
ε
Lattice-Enum 1 + d f K + x, L0 , rε0
3
outputs z ∈ CVP(K, L0 , x). Then d˜x ≤ DK,ε0 (z − x) ≤ dx0 + ε0 , as needed. If Lattice-Enum does not output
any element of CVP(K, L0 , x), we must have that (1 + ε/3)d f < dx0 and hence
d˜x ≤ (1 + ε/3)d f + ε0 < dx0 + ε0 ,
as needed.
By the construction of L0 , we also have that dx0 ≤ dx + ε/3d f ≤ (1 + 2ε/3)dx . Since dx0 ≤ d˜x + ε0 ,
we know that ((d˜x + ε0 )K + x) ∩ L 6= 0. / Therefore we are guaranteed that the final call to Lattice-
Enum((d˜x + ε0 )K + x, L0 , rε0 ) outputs all the closest vectors of L0 to x. Finally, any vector y outputted
during this call satisfies
ky − xkK ≤ d˜x + 2ε0 ≤ dx0 + 3ε0 ≤ (1 + 2ε/3)dx + (ε/3)l ≤ (1 + ε)dx ,
as needed.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 16
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Running time: We first bound the running time of each call to Lattice-Enum. Within the repeat
loop, the calls to Lattice-Enum((1 + ε/3)dK + x, L0 , rε0 ) run in 2O(n) G((1 + ε/3)dK, L0 )poly(·) time
and 2n poly(·) space. By Lemma 2.3 part 3, since (1 + ε/3) = t(ε/3) for t = (3/ε + 1), we have that
G((1 + ε/3)dK, L0 ) ≤ (4t + 2)n G((ε/3)dK, L0 ) = 6n (1 + 2/ε)n G((ε/3)dK, L0 ) = 2O(n) γ −n (1 + 1/ε)n ,
where the last inequality follows from G((ε/3)dK, L0 ) = γ −n 2O(n) by the guarantees on Lattice-Sparsifier.
Next the final call to Lattice-Enum((d˜x + ε0 )K + x, L0 , rε0 ) runs in 2O(n) G((d˜x + ε0 )K, L0 )poly(·) time
and 2n poly(·) space. Now note that ε0 ≤ (1/9)εdx , and hence
(1 + ε/3)d f ≥ dx − ε0 ≥ (1 − ε/9)dx .
From here we get that
1 − ε/9 1 − 1/9
df ≥ dx ≥ dx = 2/3dx .
1 + ε/3 1 + 1/3
Finally,
d˜x + ε0 ≤ (1 + ε/3)d f + 2ε0 ≤ (1 + ε/3)d f + 2/9εdx ≤ (1 + 2ε/3)d f .
Therefore, since (1 + 2ε/3) = t(ε/3) for t = (2 + 3/ε), by Lemma 2.3 part 3 and the guarantees on
Lattice-Sparsifier as above
G((d˜x + ε0 )K, L0 ) ≤ G((1 + 2ε/3)d f K, L0 ) ≤ (4t + 2)n G((ε/3)d f K, L0 )
= (10 + 12/ε)n G((ε/3)d f K, L0 ) = 2O(n) γ −n (1 + 1/ε)n .
Lastly, note that each call to Lattice-Sparsifier takes at most 2O(n) poly(·) time and 2n poly(·) space.
Since the repeat loop iterates polynomially many times (i. e., at most log2 (2R/r)), the total running time
is 2O(n) γ −n (1 + 1/ε)n poly(·) and the total space usage is 2n poly(·), as needed.
4 A simple randomized lattice sparsifier construction
We begin with an existence proof for lattice sparsifiers using the probabilistic method. We will use
the Cauchy-Davenport sumset inequality and another lemma in number theory about prime gaps, a
consequence of a theorem of Rosser and Schoenfeld [44, 40].2
Theorem 4.1. Let p ≥ 1 be a prime. Then for any C1 , . . . ,Ck ⊆ Z p , we have that
n k o
|C1 + · · · +Ck | ≥ min p, ∑ |Ci | − k + 1
i=1
Lemma 4.2 (Prime Gap). For every x > 1000 there exists a prime p ∈ Z satisfying x < p < 4x/3.
2 The authors are indebted to János Pintz for finding these references.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 17
DANIEL DADUSH AND G ÁBOR K UN
Proof. We will use the bounds
π(x) > x/ ln(x) if x > 17 , and π(x) < 1.25506x/ ln(x) if x > 1 ,
where π(x) denotes the number of primes less than x [44, 40]. If x > 1000 then
π(4x/3) > (4x/3)/ ln(4x/3) > 1.25506x/ ln(x) > π(x) ,
and the lemma follows.
As explained in the introduction, our sparsifiers will take the form of random sublattices. To
express these sublattices, we introduce the following notation. For a lattice L, prime number p ∈ N and
w ∈ L∗ /pL∗ , we define the sublattice
L(w, p) = {y ∈ L : hy, wi ≡ 0 (mod p)} .
To see that this is well-defined, first note that the inner products between vectors in L and L∗ are integer
valued. Second, since hy, x + zi = hy, xi (mod p) for any x ∈ L∗ , z ∈ pL∗ , one may indeed view w above
as an element of L∗ /pL∗ (any representative yields the same sublattice). Furthermore, letting B∗ denote
a basis of L∗ it is easy to check that L∗ /pL∗ = B∗ Znp .
The following theorem shows how the algebraic properties of the sparsifying vector w influence the
geometry of L(w, p). It formalises the arguments given in the introduction.
Theorem 4.3. Let K ⊆ Rn be a symmetric convex body, L ⊆ Rn an n-dimensional lattice and t ≥ 0. Let
B∗ denote a basis of L∗ and p ∈ N be an odd prime. Pick a ∈ Znp and let w = B∗ a.
Define S = {B∗T y (mod pZn ) : y ∈ L ∩ tK} ,
S0 = {z ∈ S : ha, zi ≡ 0 (mod p)} ,
R = {ha, zi : z ∈ S} .
Then, the following holds:
1. For p > |L ∩ (1 − 1/p)tK|,
(a) |S| = |L ∩ tK|,
(b) For d > 0, G(dtK, L(w, p)) ≤ (2d + 1)n |S0 |;
2. ∀ x ∈ Rn , dK (L(w, p), x) ≤ dK (L, x) + d(p − 1)/(|R| − 1)et.
Proof of 1. We first prove part (a). By the construction |S| ≤ |L ∩ tK|. We only need to show that
|S| ≥ |L ∩tK|. Assume this is not the case. Then there exists distinct x, y ∈ L ∩tK such that B∗T x ≡ B∗T y
(mod pZn ), hence x − y ∈ pL. Since x, y ∈ K, by the symmetry of K we have that x − y ∈ 2K ∩ pL.
Therefore, for every k ∈ Z, where |k| is at most (p − 1)/2, we have that
(k/p)(x − y) ∈ L ∩ (p − 1)/(2p)(2K) = L ∩ (1 − 1/p)K .
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 18
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Since x 6= y, these elements are all distinct. Therefore |L ∩ (1 − 1/p)K| ≥ 1 + 2((p − 1)/2) = p, contra-
dicting our assumption on p.
We prove part (b) now. To begin, we see that
|L(w, p) ∩ tK| = |{y ∈ L ∩ tK : hw, yi ≡ 0 (mod p)}| = |{y ∈ L ∩ tK : a, B∗T y ≡ 0 (mod p)}|
= |{z ∈ S : ha, zi ≡ 0 (mod p)}| = |S0 | .
By Lemma 2.3 part 2 we have that
G(dtK, L(w, p)) ≤ (2d + 1)n |L(w, p) ∩ tK| = (2d + 1)n |S0 | ,
as needed.
Proof of 2. Take x ∈ Rn and let y ∈ L be a closest vector to x, i. e., satisfying dK (L, x) = ky − xkK . Let
l = d(p − 1)/(|R| − 1)e. Since R ⊆ Z p , by Theorem 4.1
|R
| + ·{z
· · + R} | ≥ min{p, l(|R| − 1) + 1} = p ⇒ | + ·{z
R · · + R} = Z p .
l times l times
Therefore, by the construction of R there exist
l l
y1 , . . . , yl ∈ tK ∩ L such that hy, ai ≡ ∑ hyi , ai (mod p) ⇔ y − ∑ yi ∈ L(w, p) .
i=1 i=1
Let z = y − ∑li=1 yi . Now, by the triangle inequality and the symmetry of K we get that
l
kz − xkK ≤ ky − xkK + kz − ykK ≤ dK (L, x) + ∑ kyi kK ≤ dK (L, x) + lt ,
i=1
as needed.
The following lemma will show the existence of a vector a that can be used to build a good sparsifier.
Lemma 4.4. Let p be a prime and S ⊆ Znp satisfying 1000 < |S| < p < 4|S|/3 and 0 ∈ S. Then there
exists a ∈ Znp satisfying
1. |{y ∈ S : hy, ai ≡ 0 (mod p)}| ≤ 6,
p+2
2. |{hy, ai (mod p) : y ∈ S}| ≥ .
3
Proof. Let a denote a uniform random vector in Znp . We will show that a satisfies both conditions (1) and
(2) with non-zero probability. Let Eiy denote the indicator of the event ha, yi ≡ i for y ∈ S and i ∈ Z p .
" #
y |S| − 1
Claim 4.5. E ∑ E0 = p .
y∈S\{0}
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 19
DANIEL DADUSH AND G ÁBOR K UN
Proof of Claim 4.5. By the linearity of expectation it suffices to prove
1
E[E0y ] = Pr[ha, yi ≡ 0] =
p
for y ∈ S \ {0}. Since y 6= 0, p is a prime and a is uniform in Znp , we have that ha, yi is distributed
uniformly in Z p . Therefore Pr[ha, yi ≡ 0] = 1/p.
" #
x−y |S|2 − |S|
Claim 4.6. E ∑ 0 E = .
x,y∈S,x6=y p
Proof of Claim 4.6. If x 6= y then E[E0x−y ] = 1/p. The Claim follows by the linearity of expectation.
Returning to the proof of Lemma 4.4, we will now choose the vector a ∈ Znp . By Markov’s inequality,
|S| − 1 5
Pr {y ∈ S \ {0} : ha, yi ≡ 0} < 6 ≥ 1 − > ,
6p 6
and
5|S|2 − 5|S| 1
6|S|
Pr {(x, y) : x, y ∈ S, x 6= y, ha, xi ≡ ha, yi} ≤ ≥ 1− > .
5 6|S|p 6
Hence there exists an a such that both events hold. The first condition of the lemma is easy to check:
|{y ∈ S : hy, ai ≡ 0}| = |{y ∈ S \ {0} : hy, ai ≡ 0}| + 1 ≤ 5 + 1 = 6 .
Now we will prove the second condition using our assumption and the Cauchy-Schwarz inequality:
11|S|
≥ |{(x, y) : x, y ∈ S, x 6= y, ha, xi ≡ ha, yi}| + |S| = |{(x, y) : x, y ∈ S, ha, xi ≡ ha, yi}|
5
= ∑ |{y ∈ S : ha, yi ≡ z}|2 ≥ |S|2 /|{hy, ai (mod p) : y ∈ S}| .
z∈Z p
These yield
5|S| 15p p+2
|{hy, ai (mod p) : y ∈ S}| > > > ,
11 44 3
as needed.
We now give our first lattice sparsifier construction, which combines Theorems 4.3 and 4.4. While
we state it for symmetric norms only, it directly extends to asymmetric norms (see Lemma 3.2).
Theorem 4.7. Let K ⊆ Rn be a symmetric convex body, L ⊆ Rn an n-dimensional lattice, and t ≥ 0 a
non-negative number. Then there exists a prime p ∈ N and w ∈ L∗ /pL∗ such that
1. G(tK, L(w, p)) ≤ 1000 · 7n ,
2. ∀x ∈ Rn , dK (L(w, p), x) ≤ dK (L, x) + t.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 20
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Proof. Let N = |L ∩ (t/3)K|. If N ≤ 1000, let p = 3 and w = 0. For condition (1), by Lemma 2.3 part 2
we have that
G(tK, L) ≤ 7n |L ∩ (t/3)K| ≤ 1000 · 7n ,
as needed. Since L(w, p) = L, condition (2) trivially holds.
Now assume that N > 1000. Then by Lemma 4.2, there exists a prime p ∈ N, such that N < p <
(4/3)N. Let B∗ be a basis of L∗ and let
S = {B∗T y (mod pZn ) : y ∈ L ∩ (t/3)K} .
Then by Theorem 4.3 part 1a, we have that |S| = N. Therefore by Lemma 4.4, there exists a ∈ Znp such
that
|{z ∈ S : ha, zi ≡ 0 (mod p)}| ≤ 6 and |{ha, zi : z ∈ S}| ≥ (p + 2)/3 .
Hence by Lemma 4.3 parts 1b and 2, setting w = B∗ a, L(w, p) satisfies condition (1) with bound
6·7n < 1000·7n and condition (2) with additive error (t/3)d(p − 1)/((p + 2)/3 − 1)e = t, as needed.
5 Derandomizing the lattice sparsifier construction
We begin with a high level outline of the deterministic sparsifier construction. To recap, in the previous
section, we build a (K,t)-sparsifier for L as follows:
1. Compute N ← |tK ∩ L|. If N ≤ 1000 then return L0 = L. Else find a prime p satisfying N < p <
4N/3.
2. Build a basis B∗ ∈ Qn×n for L∗ and compute S ← {B∗T y (mod p) : y ∈ tK ∩ L}.
3. Find a vector a ∈ Znp satisfying3
p+2
(a) |{y ∈ S : ha, yi ≡ 0 (mod p)}| ≤ 6 , (b) |{ha, yi : y ∈ S}| ≥ .
3
4. Return the sublattice L0 = {y ∈ L : hy, B∗ ai ≡ 0 (mod p)}.
To implement the above construction efficiently and deterministically, we must overcome two main
obstacles. First, the construction of the vector a is probabilistic (see Lemma 4.4), and so we must
replace this with an explicit deterministic construction. For our derandomization approach, we will use
a dimension reduction strategy which will allow the vector a to be computed efficiently via exhaustive
search. We describe this method in Section 5.1. Second, the number of lattice points N in tK ∩ L could
be very large (since we have no control on t), and hence we cannot hope to directly compute the set S
efficiently via lattice point enumeration. To deal with this, we show that the sparsifier can be computed
iteratively via a “chain” of sparsifiers. This will allow us to keep t bounded by a constant times the
minimum distance of the lattice at every step, keeping the size of N bounded by 2O(n) at every step. The
details of this approach are presented in Section 5.2.
3 For slightly worse parameters, it is easy to check that a random a ∈ Zn satisfies these with constant probability.
p
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 21
DANIEL DADUSH AND G ÁBOR K UN
5.1 Deterministic construction of a good vector
We now outline our approach for deterministically implementing Lemma 4.4. As stated above, the main
idea is to use a dimension reduction procedure which allows a to be computed efficiently via exhaustive
enumeration (i. e., trying all possible a). Let N and S be as in the description. Since N < p < 4N/3, we
note that an exhaustive search over Znp requires a search over pn ≤ (4N/3)n possibilities, and the validity
check (i. e., conditions (a) and (b)) for any particular a can be implemented in poly(N) time by simple
counting. Since the existence of the desired a depends only on |S| and p (and not on n), if we can compute
a linear projection π : Znp → Zn−1 p such that |π(S)| = |S|, then we can reduce the problem to finding a
good a ∈ Zn−1 p for π(S). Indeed, such a map π can be computed efficiently and deterministically as long
as n ≥ 3. To see this, we first identify full rank n − 1 dimensional projections with their kernels, i. e., lines
through the origin in Znp . From here, we note that distinct elements x, y ∈ S collide under the projection
induced by a line l iff x − y ∈ l. Since the total number
of linesnspanned by differences of elements in S is
|S| p p
at most 2 < 2 , as long as there are at least 2 lines in Z p (for n ≥ 3) we can compute the desired
projection. Therefore, repeating the process n − 2 times, we are left with finding a good a ∈ Z2p , which
we can do by trying all p + 1 < (4N/3) + 1 lines in Z2p .
In the next section, we will show how to guarantee that N = 2O(n) , and hence the entire construction
described above will be implementable in 2O(n) time and space.
For a linear subspace S ⊆ Znp , we define its orthogonal complement
S⊥ = {y ∈ Znp : hx, yi ≡ 0 (mod p), ∀ x ∈ S} .
Since p is prime, we have the equality (S⊥ )⊥ = S. Let Lines(Znp ) denote the set of lines in Znp , i. e.,
1-dimensional linear subspaces. For a vector q ∈ Znp we denote the orthogonal complement to its linear
span qZ p by q⊥ = {y ∈ Znp : hq, yi ≡ 0 (mod p)}.
The following pseudocode implements the algorithm described above.
For the desired application of the algorithm given below, the set S above will in fact be represented
implicitly. Here the main access methodology we will require from S is a way to iterate over its elements.
In the context of (1 + ε)-CVP, the enumeration method over S will correspond to the Lattice-Enum
algorithm. Here we state the guarantees of the algorithm abstractly in terms of the number of iterations
required over S.
Theorem 5.1. Algorithm 2 is correct, and performs poly(n, log p)p4 arithmetic operations and O(np3 )
iterations over the elements of S. Furthermore, the space usage (not counting the space needed to iterate
over S) is poly(n, log p).
Analysis of Good-Vector.
Correctness: We must show that the output vector a satisfies the guarantees of Lemma 4.4:
1. |{y ∈ S : ha, yi ≡ 0 (mod p)}| ≤ 6.
p+2
2. |{ha, yi (mod p) : y ∈ S}| ≥ .
3
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 22
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
Algorithm 2 Algorithm Good-Vector(S, p)
Require: S ⊆ Znp , 0 ∈ S, integer n ≥ 1, a prime p satisfying 1000 < |S| < p < 4|S|/3.
Ensure: a ∈ Znp satisfying the conditions of Lemma 4.4 .
1: if n = 1, return 1
2: P ← In (n × n identity).
3: for n0 in n to 3 do
4: for all q ∈ Lines(Znp0 ) do
n ×(n −1) (n −1)
5: Compute a basis B ∈ Z p0 0 for q⊥ , i.e. satisfying q⊥ = BZ p 0 .
6: For all distinct x, y ∈ PS check that BT x 6≡ BT y (mod pZn0 −1 ).
If no collisions, set P ← BT P and exit loop; otherwise, continue.
7: for all q ∈ Lines(Z2p ) do
8: Pick a ∈ q \ {0}.
9: Compute zeros ← |{y ∈ PS : ha, yi ≡ 0 (mod p)}|.
10: Compute distinct ← |{ha, yi (mod p) : y ∈ PS}|.
11: if zeros ≤ 6 and distinct ≥ (p + 2)/3 then
12: return Pt a
If n = 1 then setting a ∈ Z p to 1 (i. e., line 1) trivially satisfies both conditions. We assume n ≥ 2. We
prove the following invariant for the first loop (line 2): at the beginning of each iteration, P ∈ Znp0 ×n and
|PS| = |S|.
n ×(n −1)
First let us assume that during the loop iteration, we find B ∈ Z p0 0 satisfying BT x 6= BT y for
all distinct x, y ∈ PS (verified in line 5). This yields that the map x → BT x is injective when restricted
n ×(n −1)
to PS, and hence |BT PS| = |S|. Next, since B ∈ Z p0 0 and P ∈ Znp0 ×n , we have that P is set to
(n −1)×n
BT P ∈ Z p 0 for the next iteration, as needed.
Now we show that a valid projection matrix BT is guaranteed to exist as long as n0 ≥ 3. First, we
claim that there exists q ∈ Lines(Znp0 ), such that for all distinct x, y ∈ PS, (q + x) ∩ (q + y) = 0,
/ i.e. all
the lines passing through PS in the direction q are disjoint. A line q fails to satisfy this condition if and
only if x − y ∈ q for distinct x, y ∈ PS. The number of lines that can be generated in this way from PS is
at most
|PS| |S|
= < p(p − 1)/2 .
2 2
Since
pn0 − 1 p(p − 1)
|Lines(Znp0 )| = >
p−1 2
n ×(n −1)
for n0 ≥ 3 we may pick q ∈ Lines(Znp ) that satisfies the condition. Now let B ∈ Z p0 0 denote a basis
⊥ n −1 T
satisfying q = BZ p . We claim that |B PS| = |PS|. Assume not then there exists distinct x, y ∈ PS
0
such that
BT x ≡ BT y ⇔ BT (x − y) ≡ 0 ⇔ (x − y) ∈ (BZnp0 −1 )⊥ = q ,
which contradicts our assumption on q. Therefore, the algorithm is indeed guaranteed to find a valid
projection, as needed.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 23
DANIEL DADUSH AND G ÁBOR K UN
After the first for loop, we have constructed P ∈ Z2×np satisfying |PS| = |S|, where |S| < p < 4|S|/3.
By Lemma 4.4, there exists a ∈ Z2p satisfying (1) and (2) for the set PS. Since (1) and (2) hold for any
non-zero multiple of a, i. e., any vector defining the same line as a, we may restrict the search to elements
of Lines(Z2p ). Therefore, by trying all p + 1 elements of Lines(Z2p ) the algorithm is guaranteed to find a
valid a for the PS. Noting that ha, Pyi ≡ PT a, y , we get that PT a satisfies (1) and (2) for the set S, as
needed.
Running time: For n = 1 the running time is constant. We assume n ≥ 2. Here the first for loop is
executed n − 2 times. For each loop iteration we run though q ∈ Lines(Znp0 ) until we find one inducing
a good projection matrix B. From the above analysis, we iterate through at most |S|
2 < p(p − 1)/2
elements q ∈ Lines(Znp0 ) before finding a good projection matrix. For each q, we build a basis matrix B
for q⊥ which can be done using poly(n, log p) arithmetic operations. Next, we check for collisions against
each pair x, y ∈ PS, which can be done using O(|S|) = O(p) iterations over S. Therefore, at each loop
iteration we enumerate over S at most p3 times while performing only polynomial-time computations.
Hence, the total number of operations (excluding the time needed to output the elements of S) is at most
poly(n, log p)p4 .
For the last phase, we run through the elements in Lines(Z2p ), where |Lines(Z2p )| = p + 1. The
validity check for a ∈ Lines(Z2p ) requires computing both the quantities (1) and (2). To compute
|{y ∈ S : hy, ai ≡ 0 (mod p)}| we iterate once over the set S and count how many zero dot products
there are. To compute |{ha, yi : y ∈ S}|, we first iterate over all residues in Z p . Next, for each residue
i ∈ Z p , if we find y ∈ S satisfying ha, yi ≡ i (mod p), we increment our counter by one, and otherwise
continue. Hence for any specific a ∈ Z2p , we iterate over the set S exactly p + 1 times, performing
poly(n, log p)p2 operations. Hence, over the whole loop we perform O(p2 ) iterations over the set S, and
perform poly(n, log p)p3 operations.
Therefore, over the whole algorithm we iterate over the set S at most np3 times, and perform at most
poly(n, log p)p4 operations. Furthermore, not counting the space needed to iterate over the set S, the
space used by the algorithm is poly(n, log p).
5.2 Deterministic sparsifier construction
We now detail how to iteratively use the Good-Vector algorithm to get a completely deterministic lattice
sparsifier construction.
To assure that we never need to apply the Good-Vector algorithm to a set S of size larger than 2O(n) ,
we will build the (K,t)-sparsifier iteratively. In particular, we will compute a sequence of sparsifiers
L1 , . . . , Lk , satisfying that Li is a (K, ci λ )-sparsifier for Li−1 for i ≥ 1, where L0 = L, λ = λ1 (K, L) and
c > 1 is a constant. Here we start the sparsification process at the minimum distance of L and increase
the sparsification distance by a constant factor at each step. To build the sparsifier Li , i ≥ 1, Good-Vector
will (roughly speaking) only need to enumerate from the set Li−1 ∩ ci λ K which contains at most
G(ci λ K, Li−1 ) ≤ (4c + 2)n G(ci−1 λ K, Li−1 ) = 2O(n)
points (by Lemma 2.3 part 3), since Li−1 is a (K, ci−1 λ )-sparsifier. Hence we will be able to guarantee
that the number of lattice points we process at each step is 2O(n) . Furthermore, the geometric growth rate
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 24
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
in the sparsification distance will allow us to conclude that Li is in fact a (K, (ci+1 /(c − 1))λ )-sparsifier
for L. Hence, iterating the process O(ln(t/λ1 )) times will yield the final desired sparsifier.
Algorithm 3 Algorithm Lattice-Sparsifier(K, L, t)
Require: (0, r, R)-centered convex body K ⊆ Rn with distance oracle DK,· for k · kK , basis B ∈ Qn×n for
L, and t ≥ 0.
Ensure: (K,t)-sparsifier for L.
1: K ← K ∩ −K.
2: Compute y ∈ Shortest-Vectors(K, L, 1/3).
3: λ ← DK,1/2 (y); ε ← 7−(n+5) .
4: k ← bln 32 λt + 1 / ln 3c.
5: L0 ← L; B0 ← B.
6: for i in 0 to k − 1 do
7: S̄ ← Lattice-Enum(3i (1 − ε)λ K, Li , ελ r).
8: Compute N ← |S̄|.
9: if N > 1000 then
10: Compute B∗i ← B−T i , a basis for Li .
∗
11: Compute prime p satisfying N < p < 4N/3.
12: a ← Good-Vector(B∗T n
i S̄ (mod pZ ), p).
13: Compute Li+1 ← {y ∈ Li : hBi a, yi ≡ 0 (mod p)} and basis Bi+1 for Li+1 .
∗
14: else
15: Li+1 ← Li ; Bi+1 ← Bi .
16: return Lk
The pseudocode in Algorithm 3 implements the above algorithm. The correctness and running time
bound of this algorithm will yield the proof of Theorem 3.3. We begin its analysis with the following
lemma. We remark that the lemma works on K ∩ −K, the symmetrized version of K.
Lemma 5.2. Let i denote the iteration of the for loop at line 6, and let the variables be defined as in each
iteration. For i ∈ {0, . . . , k}, the following holds:
1. G(3i λ K, Li ) ≤ 7n+4 ;
3
2. ∀x ∈ Rn , dK (Li , x) ≤ dK (L, x) + (3i − 1)λ .
2
Proof. We first claim that λ satisfies λ1 (K, L)/2 ≤ λ ≤ 2λ1 (K, L). Here, we have that
4
kykK ≤ λ1 (K, L)
3
by the guarantee on Shortest-Vector(K, L, 1/3). By the guarantees on DK,1/2 , we have that λ = DK,1/2 (y)
satisfies
3
λ1 (K, L)/2 ≤ kykK /2 ≤ λ ≤ kykK ≤ 2λ1 (K, L) ,
2
as needed.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 25
DANIEL DADUSH AND G ÁBOR K UN
We now establish the lemma by induction on i. For i = 0, we have that L0 = L. Since λ ≤ 2λ1 (K, L),
by Lemma 2.3 part 1 we have that G(λ K, L0 ) ≤ (2 · 2 + 1)n = 5n < 7n+4 . Hence L0 satisfies (2).
Furthermore, since L0 = L, we have that L0 trivially satisfies property (2).
We now prove the claim for i ≥ 1. Let S̄ denote the set outputted by
Lattice-Enum(3i−1 (1 − ε)λ K, Li−1 , ελ r) .
By the guarantees on Lattice-Enum, the set S̄ satisfies
3i−1 (1 − ε)λ K ∩ Li−1 ⊆ S ⊆ (3i−1 (1 − ε)λ K + ελ rBn2 ) ∩ Li−1 .
Since rBn2 ⊆ K and i ≥ 1 we have 3i−1 (1 − ε)λ K + ελ rBn2 ⊆ 3i−1 λ K. Therefore,
3i−1 (1 − ε)λ K ∩ Li−1 ⊆ S̄ ⊆ 3i−1 λ K ∩ Li−1 . (5.1)
Set N = |S̄| (line 8). By (5.1) and the induction hypothesis we have
|3i−1 (1 − ε)λ K ∩ Li−1 | ≤ N ≤ |3i−1 λ K ∩ Li−1 | ≤ G(3i−1 λ K, Li−1 ) ≤ 7n+4 .
Assume N ≤ 1000. Then the algorithm sets Li = Li−1 and Bi = Bi−1 . By (5.1), we have that
|3i−1 (1 − ε)λ K ∩ Li | ≤ N ≤ 1000. Therefore, Lemma 2.3 part 2 yields
G(3i λ K, Li ) ≤ (2 · 3(1/(1 − ε)) + 1)n |3i−1 (1 − ε)λ K ∩ Li−1 |
≤ 7n (1 + 2ε)n · 1000 ≤ 7n+4 ,
where the last two inequalities follow since ε ≤ 7−(n+5) . Therefore Li satisfies condition (1), as needed.
Furthermore, since Li = Li−1 , the induction hypothesis trivially implies that Li satisfies condition (2).
Assume N > 1000. Here, we first compute a prime p ∈ N satisfying N < p < 4N/3 < 1/ε, and a
dual basis B∗i−1 for L∗i−1 . Let S = B∗T n
i−1 S̄ (mod pZ ). By Theorem 4.3 and Equation (5.1), since
p > |S̄| ≥ |Li−1 ∩ 3i−1 (1 − ε)λ K| ≥ |Li−1 ∩ 3i−1 (1 − 1/p)λ K|
we have that |S| = N. Therefore Good-Vector applied to S returns a vector a ∈ Znp satisfying
a. |{y ∈ 3i−1 (1 − ε)λ K ∩ Li−1 : hB∗ a, yi ≡ 0 (mod p)}| ≤ 6,
p+2
b. |{hB∗ a, yi (mod p) : y ∈ 3i−1 λ K ∩ Li−1 }| ≥ .
3
We recall that Li = {y ∈ Li−1 : hB∗ a, yi = 0 (mod p)}. Using (a) above and Theorem 4.3 part 1b we
have that
G(3i λ K, Li ) ≤ (2 · 3 · (1/(1 − ε)) + 1)n |3i−1 (1 − ε)λ K ∩ Li |
≤ 7n (1 + 2ε)n · 6 < 7n+4 .
Therefore Li satisfies condition (1). By (b) above and part 2 of Theorem 4.3 we have that
dK (Li , x) ≤ dK (Li−1 , x) + 3i λ .
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 26
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
The induction hypothesis on Li−1 implies that
3 3
dK (Li , x) ≤ dK (Li−1 , x) + 3i λ ≤ dK (L, x) + (3i−1 − 1)λ + 3i λ = dK (L, x) + (3i − 1)λ .
2 2
Therefore Li satisfies condition (2), as needed. The lemma thus follows.
Proof of Theorem 3.3 (Lattice Sparsifier Construction).
Correctness: We show that the outputted lattice is a (K,t)-sparsifier for L. By Lemma 3.2 it suffices
to show that the algorithm outputs a (K ∩ −K,t)-sparsifier, which justifies the switch in line 2 from K to
K ∩ −K. In what follows, we therefore assume that K is symmetric.
Given Lemma 2, we will show that Lk is a (K,t)-sparsifier for L. By our choice of k, note that
3 k 3
(3 − 1)λ ≤ t ≤ (3k+1 − 1)λ .
2 2
By Lemma 2, for x ∈ Rn ,
3
dK (Lk , x) ≤ dK (L, x) + (3k − 1)λ ≤ dK (L, x) + t .
2
It therefore only remains to bound G(tK, Lk ). By the previous bounds
t 3 (3k+1 − 1)λ 9
≤ < .
3k λ 2 k
3λ 2
Therefore, Lemma 2.3 part 3 implies that
n
9
G(tK, Lk ) ≤ 4 · + 2 G(3k λ K, Lk ) ≤ (20)n · 7n+4 = 2O(n) ,
2
as needed. The algorithm returns a valid (K,t)-sparsifier for L.
Running time: The algorithm first runs the Shortest-Vectors on K and L, which takes 2O(n) poly(·)
time and 2n poly(·) space. Next, the for loop on line 6 iterates
2t
k = ln + 1 / ln 3 = poly(·)
3λ
times.
Each for loop iteration, indexed by i satisfying 0 ≤ i ≤ k − 1, consists of computations over the set
S̄ ← Lattice-Enum(3i (1 − ε)λ K, Li , ελ r). For the intended implementation, we do not store the set S̄
explicitly. Every time the algorithm needs to iterate over S̄, we implement this by performing a call to
Lattice-Enum(3i (1 − ε)λ K, Li , ελ r). Furthermore, the algorithm only interacts with S̄ by iterating over
its elements, and hence the implemented interface suffices. Now at the loop iteration indexed by i, we do
as follows:
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 27
DANIEL DADUSH AND G ÁBOR K UN
1. Compute N = |S̄|. This is implemented by iterating over the elements of S̄ and counting, and
so by the guarantees of Lattice-Enum requires at most 2O(n) G(3i λ K, Li ) poly(·) = 2O(n) poly(·)
time—-by Lemma 2 part 1—and 2n poly(·) space.
2. If N ≤ 1000, we keep the same lattice and skip to the next loop iteration. If N > 1000, continue.
3. Compute B∗i = B−T
i . This can be done in poly(·) time and space.
4. Compute a prime p satisfying N < p < 4N/3. Such a prime can be computed by trying all integers
in the previous range and using trial division. This takes at most O(N 2 poly(log N)) = 2O(n) time
and poly(n) space.
5. Call Good-Vector(BT ∗ S̄ (mod pZn ), p). By the guarantees on Good-Vector, the algorithm per-
forms poly(n, log p)p4 = 2O(n) operations and iterates at most np3 = 2O(n) times over the set BT ∗ S̄
(mod pZn ). These iterations can be performed in 2O(n) poly(·) time and 2n poly(·) space by the
guarantees on Lattice-Enum.
6. Compute a basis Bi+1 for the new lattice Li+1 = {y ∈ Li : B∗T a, y ≡ 0 (mod p)}. This can be
done in poly(·) time.
From the above analysis, we see that the entire algorithm runs in 2O(n) poly(·) time and 2n poly(·)
space as needed.
6 Further applications and future directions
Integer programming. We explain how the techniques in this paper apply to Integer Programming (IP),
i. e., the problem of deciding whether a polytope contains an integer point, and discuss some potential
associated avenues for improving the complexity of IP. For a brief history, the first breakthrough works
on IP are by Lenstra [32] and Kannan [27], where it was shown that any n-variable IP can be solved in
2O(n) n2.5n time (with polynomial dependencies on the remaining parameters). Since then, progress on
IP has been slow, though recent complexity improvements have been made: the dependence on n was
4
reduced to n2n [24], Õ(n) 3 n [12], and finally nn [10].
Let K ⊆ Rn denote a polytope. To find an integer point inside K, the general outline of the above
algorithms is as follows. Pick a center point c ∈ K, and attempt to “round” c to a point in Zn inside K. If
this fails, decompose the integer program on K into subproblems. Here, the decomposition is generally
achieved by partitioning Zn along shifts of some rational linear subspace H (often a hyperplane) and
recursing on the integral shifts of H intersecting K.
In [11], an algorithm is given to perform the above rounding step in a “near-optimal” manner. More
precisely, the center c of K is chosen to be the center of gravity b of K (which can be estimated via
random sampling), and rounding b to Zn is done via an approximate CVP computation with target
b, lattice Zn , and norm k · kK−b (corresponding to scaling K about b(K)). Here the AKS randomized
sieve is used to perform the approximate CVP computation, which is efficient due to the fact that K − b
is near-symmetric (see [39]). Let y ∈ Zn be the returned (1 + ε)-CVP solution, and assume that y is
correctly computed (which occurs with high probability). We can now examine the following cases.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 28
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
If y ∈ K, we have solved the IP. If ky − bkK−b > (1 + ε), then by the guarantee on y, for any z ∈ Zn
we have that kz − bkK−b > 1 ⇔ z ∈ / K. Hence, we can immediately decide that K ∩ Zn = 0. / Lastly, if
1 < ky − bkK−b ≤ (1 + ε), we know that
1 ε
K+ b
1+ε 1+ε
is integer-free while (1 + ε)K − εb contains y. In this final case, we are in essentially a near-optimal
situation for computing a “good” decomposition (using the so-called “flatness” theorems in the geometry
of numbers). We note that with previous methods (i. e., using only symmetric norm or `2 techniques), the
ratio of scalings between the integer-free and not integer-free case was O(n) in the worst case as opposed
to (1 + ε)2 (here ε can be any constant ≤ 1).
With the techniques in this paper, we note that the above rounding procedure can be made Las
Vegas (i. e., no probability of error, randomized running time) by replacing the AKS Sieve with our
new DPV-based solver (randomness is still needed to estimate the center of gravity). This removes
any probability of error in the above inferences, making the above rounding algorithm easier to apply
in the IP setting. We note that the geometry induced by the above rounding procedure is currently
poorly understood, and very little of it is being exploited by IP algorithms. One hope for improving the
complexity of IP with the above methods, is that with a strong rounding procedure as above one may
be able to avoid the worst case bounds on the number of subproblems created at every recursion node.
Currently, the main way to show that K admits a small decomposition into subproblems is to show that
the covering radius of K (i. e., the minimum scaling such that every shift of K intersects Zn ) is large.
Using the above techniques, we easily get that in the final case the covering radius is at least 1/(1 + ε)
(since (1/(1 + ε))K + (ε/(1 + ε))b is integer-free), however in reality the covering radius could be much
larger (yielding smaller decompositions). An interesting direction would be to try and show that on the
aggregate (over all subproblems), the covering radii of the nodes must grow as we go down the recursion
tree. This would allow us to show that as we descend the recursion tree, the branching factor shrinks
quickly, allowing us to get better bounds on the size of the recursion tree (which yields the dominant
complexity term for current IP algorithms).
CVP under `∞ . While the ideas presented here do not seem to be practically implementable in general
(at least currently), there are special cases where the overhead incurred by our approach may be acceptable.
One potential target is solving (1 + ε)-CVP under `∞ . This is one of the most useful norms that is often
approximated by `2 for lack of a better alternative.
As an example, in [8], they reduce the problem of computing machine-efficient polynomial approxi-
mations (i. e., having small coefficient sizes) of 1-dimensional functions to CVP under `∞ . The goal in
this setting is to generate a high quality approximation that is suitable for hardware implementation or
for use in a software library, and hence spending considerable computational resources to generate it is
justified.
We now explain why the `∞ norm version of our algorithms may be suitable for practical imple-
mentation (or at least efficient “heuristic” implementation). Most importantly, for `∞ the DPV lattice
point enumerator is trivial to implement. In particular, to enumerate the lattice points in a cube, one
simply enumerates the points in the outer containing ball and retains those in the cube. Second, if one is
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 29
DANIEL DADUSH AND G ÁBOR K UN
comfortable with randomization, the sparsifier can be constructed by adding a simple random modular
form to the base lattice. For provable guarantees, the main issue is that the modulus must be carefully
chosen (see Section 4), however it seems plausible that in practice an appropriate modulus may be guessed
heuristically.
Acknowledgments. We are very grateful to the anonymous referees for their comments and suggestions
which greatly helped us improve the quality of the presentation.
References
[1] M IKLÓS A JTAI: The shortest vector problem in L2 is NP-hard for randomized reductions (extended
abstract). In Proc. 30th STOC, pp. 10–19. ACM Press, 1998. [doi:10.1145/276698.276705] 2
[2] M IKLÓS A JTAI , R AVI K UMAR , AND D. S IVAKUMAR: A sieve algorithm for the shortest lattice
vector problem. In Proc. 33rd STOC, pp. 601–610. ACM Press, 2001. [doi:10.1145/380752.380857]
3
[3] M IKLÓS A JTAI , R AVI K UMAR , AND D. S IVAKUMAR: Sampling short lattice vectors and the
closest lattice vector problem. In Proc. 17th IEEE Conf. on Computational Complexity (CCC’02),
pp. 53–57. IEEE Comp. Soc. Press, 2002. [doi:10.1109/CCC.2002.1004339] 3
[4] S ANJEEV A RORA , L ÁSZLÓ BABAI , JACQUES S TERN , AND Z. S WEEDYK: The hardness of
approximate optima in lattices, codes, and systems of linear equations. J. Comput. System Sci.,
54(2):317–331, 1997. Preliminary version in FOCS’93. [doi:10.1006/jcss.1997.1472] 2
[5] V IKRAMAN A RVIND AND P USHKAR S. J OGLEKAR: Some sieving algorithms for lattice problems.
In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer
Science (FSTTCS’08), volume 2 of LIPIcs, pp. 25–36. Schloss Dagstuhl - Leibniz-Zentrum fuer
Informatik, 2008. [doi:10.4230/LIPIcs.FSTTCS.2008.1738] 3
[6] L ÁSZLÓ BABAI: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica,
6(1):1–13, 1986. Preliminary version in STACS’85. [doi:10.1007/BF02579403] 3
[7] J OHANNES B LÖMER AND S TEFANIE NAEWE: Sampling methods for shortest vectors, closest
vectors and successive minima. Theoret. Comput. Sci., 410(18):1648–1665, 2009. Preliminary
version in ICALP’07. [doi:10.1016/j.tcs.2008.12.045] 3
[8] N ICOLAS B RISEBARRE AND S YLVAIN C HEVILLARD: Efficient polynomial L∞ -approximations.
In 18th IEEE Symposium on Computer Arithmetic (ARITH’07), pp. 169–176. IEEE Comp. Soc.
Press, 2007. [doi:10.1109/ARITH.2007.17] 29
[9] J IN -Y I C AI AND A JAY N ERURKAR: Approximating the SVP to within a factor (1+1/dimε ) is
NP-hard under randomized reductions. J. Comput. System Sci., 59(2):221–239, 1999. Preliminary
version in CCC’98. [doi:10.1006/jcss.1999.1649] 2
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 30
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
[10] DANIEL DADUSH: Integer Programming, Lattice Algorithms, and Deterministic Volume Estimation.
Ph. D. thesis, Georgia Institute of Technology, 2012. Available at author’s webpage. 2, 4, 6, 11, 13,
28
[11] DANIEL DADUSH: A randomized sieving algorithm for approximate integer programming. Algorith-
mica, 70(2):208–244, 2014. Preliminary version in LATIN’12. [doi:10.1007/s00453-013-9834-8]
2, 3, 4, 6, 28
[12] DANIEL DADUSH , C HRIS P EIKERT, AND S ANTOSH V EMPALA: Enumerative lattice algorithms in
any norm via M-ellipsoid coverings. In Proc. 52rd FOCS, pp. 580–589. IEEE Comp. Soc. Press,
2011. [doi:10.1109/FOCS.2011.31, arXiv:abs/1011.5666] 2, 4, 5, 13, 28
[13] DANIEL DADUSH AND S ANTOSH S. V EMPALA: Near-optimal deterministic algorithms for vol-
ume computation via M-ellipsoids. Proceedings of the National Academy of Sciences, 2013.
[doi:10.1073/pnas.1203863110] 4
[14] I RIT D INUR: Approximating SVP∞ to within almost-polynomial factors is NP-hard. Theoret. Com-
put. Sci., 285(1):55–71, 2002. Preliminary versions in CIAC’00 and ECCC. [doi:10.1016/S0304-
3975(01)00290-0] 2
[15] I RIT D INUR , G UY K INDLER , R AN R AZ , AND S HMUEL S AFRA: Approximating CVP to within
almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003. Preliminary version
in FOCS’98. [doi:10.1007/s00493-003-0019-y] 2
[16] F RIEDRICH E ISENBRAND , N ICOLAI H ÄHNLE , AND M ARTIN N IEMEIER: Covering cubes and the
closest vector problem. In Proc. 27th Symp. on Computational Geometry (SoCG’11), pp. 417–423.
ACM Press, 2011. [doi:10.1145/1998196.1998264, arXiv:1012.2289] 3
[17] P ETER VAN E MDE B OAS: Another NP-complete partition problem and the complexity of computing
short vectors in a lattice. Technical Report 81-04, University of Amsterdam, 1981. Available at
author’s webpage. 2
[18] A NDRÁS F RANK AND É VA TARDOS: An application of simultaneous diophantine approximation
in combinatorial optimization. Combinatorica, 7(1):49–65, 1987. [doi:10.1007/BF02579200] 2
[19] O DED G OLDREICH , DANIELE M ICCIANCIO , S HMUEL S AFRA , AND J EAN -P IERRE S EIFERT:
Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.
Inform. Process. Lett., 71(2):55–61, 1999. [doi:10.1016/S0020-0190(99)00083-6] 5
[20] G UILLAUME H ANROT, X AVIER P UJOL , AND DAMIEN S TEHLÉ: Algorithms for the shortest and
closest lattice vector problems. In IWCC 2011, volume 6639 of LNCS, pp. 159–190. Springer, 2011.
[doi:10.1007/978-3-642-20901-7_10] 3
[21] G UILLAUME H ANROT AND DAMIEN S TEHLÉ: Improved analysis of Kannan’s Shortest Lattice
Vector algorithm. In Advances in Cryptology (CRYPTO) 2007, 27th Internat. Cryptology Conf.,
volume 4622 of LNCS, pp. 170–186. Springer, 2007. [doi:10.1007/978-3-540-74143-5_10] 3
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 31
DANIEL DADUSH AND G ÁBOR K UN
[22] I SHAY H AVIV AND O DED R EGEV: Tensor-based hardness of the shortest vector problem to within
almost polynomial factors. Theory of Computing, 8(1):513–531, 2012. Preliminary version in
STOC’07. [doi:10.4086/toc.2012.v008a023] 2
[23] B ETTINA H ELFRICH: Algorithms to construct Minkowski reduced and Hermite reduced lattice
bases. Theoret. Comput. Sci., 41:125–139, 1985. [doi:10.1016/0304-3975(85)90067-2] 3
[24] ROBERT H ILDEBRAND AND M ATTHIAS K ÖPPE: A new Lenstra-type algorithm for quasiconvex
polynomial integer minimization with complexity 2O(n log n) . Discrete Optimization, 10(1):69–84,
2013. [doi:10.1016/j.disopt.2012.11.003, arXiv:1006.4661] 3, 28
[25] A NTOINE J OUX AND JACQUES S TERN: Lattice reduction: A toolbox for the cryptanalyst. J.
Cryptology, 11(3):161–185, 1998. [doi:10.1007/s001459900042] 2
[26] M ICHAEL K AIB AND H ARALD R ITTER: Block reduction for arbitrary norms. Manuscript, 1995.
Available at the Goethe-Universität webpage. 3
[27] R AVI K ANNAN: Minkowski’s convex body theorem and integer programming. Math. Oper. Res.,
12(3):415–440, 1987. [doi:10.1287/moor.12.3.415] 2, 3, 6, 28
[28] R AVI K ANNAN: Lattice translates of a polytope and the Frobenius problem. Combinatorica,
12(2):161–177, 1992. Preliminary version in FSTTCS’89. [doi:10.1007/BF01204720] 2
[29] S UBHASH K HOT: Hardness of approximating the shortest vector problem in lattices. J. ACM,
52(5):789–808, 2005. Preliminary version in FOCS’04. [doi:10.1145/1089023.1089027] 2, 6
[30] S UBHASH K HOT: Hardness of approximating the shortest vector problem in high L p
norms. J. Comput. System Sci., 72(2):206–219, 2006. Preliminary version in FOCS’03.
[doi:10.1016/j.jcss.2005.07.002] 6
[31] A RJEN K. L ENSTRA , H ENDRIK W. L ENSTRA , J R ., AND L ÁSZLÓ L OVÁSZ: Factoring
polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
[doi:10.1007/BF01457454] 2, 3
[32] H ENDRIK W. L ENSTRA: Integer programming with a fixed number of variables. Math. Oper. Res.,
8(4):538–548, 1983. [doi:10.1287/moor.8.4.538] 2, 28
[33] L ÁSZLÓ L OVÁSZ AND H ERBERT E. S CARF: The generalized basis reduction algorithm. Math.
Oper. Res., 17(3):751–764, 1992. [doi:10.1287/moor.17.3.751] 3
[34] DANIELE M ICCIANCIO: The shortest vector in a lattice is hard to approximate to within
some constant. SIAM J. Comput., 30(6):2008–2035, 2000. Preliminary version in FOCS’98.
[doi:10.1137/S0097539700373039] 2
[35] DANIELE M ICCIANCIO: Inapproximability of the shortest vector problem: Toward a determin-
istic reduction. Theory of Computing, 8(22):487–512, 2012. Preliminary version in ECCC.
[doi:10.4086/toc.2012.v008a022] 2
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 32
L ATTICE S PARSIFICATION AND THE A PPROXIMATE C LOSEST V ECTOR P ROBLEM
[36] DANIELE M ICCIANCIO AND S HAFI G OLDWASSER: Complexity of Lattice Problems: a cryp-
tographic perspective. Volume 671 of The Kluwer Internat. Series in Engineering and Comput.
Science. Kluwer, 2002. [doi:10.1007/978-1-4615-0897-7] 3
[37] DANIELE M ICCIANCIO AND PANAGIOTIS VOULGARIS: A deterministic single exponential time
algorithm for most lattice problems based on Voronoi cell computations. SIAM J. Comput.,
42(3):1364–1391, 2013. Preliminary version in STOC’10. [doi:10.1137/100811970] 3, 5
[38] DANIELE M ICCIANCIO AND M ICHAEL WALTER: Fast lattice point enumeration with minimal
overhead. In Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pp. 276–294.
ACM Press, 2015. [doi:10.1137/1.9781611973730.21] 3
[39] V ITALI D. M ILMAN AND A LAIN PAJOR: Entropy and asymptotic geometry of non-symmetric
convex bodies. Advances in Mathematics, 152(2):314–335, 2000. [doi:10.1006/aima.1999.1903] 3,
28
[40] W ŁADYSŁAW NARKIEWICZ: The Development of Prime Number Theory, From Euclid to Hardy
and Littlewood. Springer, 2000. [doi:10.1007/978-3-662-13157-2] 17, 18
[41] P HONG Q. N GUYEN AND JACQUES S TERN: The two faces of lattices in cryptology. In Cryptogra-
phy and Lattices (CaLC’01), volume 2146 of LNCS, pp. 146–180. Springer, 2001. [doi:10.1007/3-
540-44670-2_12] 2
[42] A NDREW M ICHAEL O DLYZKO: The rise and fall of knapsack cryptosystems. In Cryptology and
Computational Number Theory, volume 42 of Proceedings of Symposia in Applied Mathematics, pp.
75–88, 1990. Available at author’s webpage. 2
[43] O DED R EGEV AND R ICKY ROSEN: Lattice problems and norm embeddings. In Proc. 38th STOC,
pp. 447–456. ACM Press, 2006. [doi:10.1145/1132516.1132581] 2
[44] J OHN BARKLEY ROSSER AND L OWELL S CHOENFELD: Approximate formulas for some functions
of prime numbers. Illinois J. Math., 6(1):64–94, 1962. Available at Project Euclid. 17, 18
[45] C LAUS -P ETER S CHNORR: A hierarchy of polynomial time lattice basis reduction algorithms.
Theoret. Comput. Sci., 53(2-3):201–224, 1987. [doi:10.1016/0304-3975(87)90064-8] 3
[46] C LAUS -P ETER S CHNORR: Factoring integers and computing discrete logarithms via diophantine
approximation. In Advances in Cryptology (EUROCRYPT’91), volume 547 of LNCS, pp. 281–293.
Springer, 1991. [doi:10.1007/3-540-46416-6_24] 2
[47] M ARTIN S EYSEN: Simultaneous reduction of a lattice basis and its reciprocal basis. Combinatorica,
13(3):363–376, 1993. [doi:10.1007/BF01202355] 7
[48] E MANUELE V ITERBO AND J OSEPH B OUTROS: A universal lattice code decoder for fading
channels. IEEE Trans. Inform. Theory, 45(5):1639–1642, 1999. [doi:10.1109/18.771234] 2
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 33
DANIEL DADUSH AND G ÁBOR K UN
AUTHORS
Daniel Dadush
Tenure Track Researcher
Centrum Wiskunde & Informatica (CWI)
Amsterdam, The Netherlands
dadush cwi nl
http://homepages.cwi.nl/~dadush/
Gábor Kun
Alfréd Rényi Institute of Mathematics
Hungarian Academy of Sciences
13-15 Reáltanoda u., Budapest, Hungary 1053
kungabor renyi hu
http://www.renyi.hu/~kungabor/
ABOUT THE AUTHORS
DANIEL DADUSH is a tenure track researcher at the Centrum Wiskunde & Informatica (CWI)
in Amsterdam. He earned his Ph. D. in algorithms, combinatorics and optimization (ACO)
from Georgia Tech in 2012, where his advisor was Santosh Vempala. Before joining
CWI, he spent two years as a Simons postdoctoral fellow in the Computer Science
Department at New York University. His research has focused on algorithms for lattice
problems, integer programming, and high-dimensional convex geometry. He lives and
works in Amsterdam, and is glad that, thus far, the city remains above water level. He
enjoys reading the New York Times, listening to NPR, and taking long bike rides through
the canals when it is not raining.
G ÁBOR K UN works at the Rényi Institute in Budapest. He earned his Ph. D. at Eötvös
University, Budapest, where his advisor was Csaba Szabó. This makes him László
Babai’s mathematical great-grandchild. In his thesis he studied constraint satisfaction
problems in terms of logic; he derandomized the reduction that led Feder and Vardi to the
CSP dichotomy conjecture. He was a postdoc at DIMACS, the Institute for Advanced
Study, and Simon Fraser University and held visiting positions at Charles University
(Prague), the Courant Institute, the University of Cambridge, and the University of
Memphis. In his spare time he likes to do sports: bridge, soccer, hiking, swimming, and
especially chess.
T HEORY OF C OMPUTING, Volume 12 (2), 2016, pp. 1–34 34