On the Quantitative Hardness of CVP
Huck Bennett∗
huckbennett@gmail.com

Alexander Golovnev†‡
alexgolovnev@gmail.com

Noah Stephens-Davidowitz∗§
noahsd@gmail.com

arXiv:1704.03928v2 [cs.CC] 5 Oct 2017

Abstract
For odd integers p ≥ 1 (and p = ∞), we show that the Closest Vector Problem in the `p
norm (CVPp ) over rank n lattices cannot be solved in 2(1−ε)n time for any constant ε > 0 unless
the Strong Exponential Time Hypothesis (SETH) fails. We then extend this result to “almost all”
values of p ≥ 1, not including the even integers. This comes tantalizingly close to settling the
quantitative time complexity of the important special case of CVP2 (i.e., CVP in the Euclidean
norm), for which a 2n+o(n) -time algorithm is known. In particular, our result applies for any
p = p(n) 6= 2 that approaches 2 as n → ∞.
We also show a similar SETH-hardness result for SVP∞ ; hardness of approximating CVPp
to within some constant factor under the so-called Gap-ETH assumption; and other quantitative
hardness results for CVPp and CVPPp for any 1 ≤ p < ∞ under different assumptions.

∗

Courant Institute of Mathematical Sciences, New York University.
Yahoo Research.
‡
Part of this work was done while the author was at Courant Institute of Mathematical Sciences, and was supported
by the National Science Foundation under Grant No. CCF-1320188. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the
National Science Foundation.
§
Supported by the National Science Foundation (NSF) under Grant No. CCF-1320188, and the Defense Advanced
Research Projects Agency (DARPA) and Army Research Office (ARO) under Contract No. W911NF-15-C-0236.
†

1

Introduction

A lattice L is the set of all integer combinations of linearly independent basis vectors b1 , . . . , bn ∈ Rd ,
L = L(b1 , . . . , bn ) :=

n
nX

o

zi bi : zi ∈ Z .

i=1

We call n the rank of the lattice L and d the dimension or the ambient dimension.
The two most important computational problems on lattices are the Shortest Vector Problem
(SVP) and the Closest Vector Problem (CVP). Given a basis for a lattice L ⊂ Rd , SVP asks us to
compute the minimal length of a non-zero vector in L, and CVP asks us to compute the distance
from some target point t ∈ Rd to the lattice. Typically, we define length and distance in terms of
the `p norm for some 1 ≤ p ≤ ∞, given by
kxkp := (|x1 |p + |x2 |p + · · · + |xd |p )1/p
for finite p and
kxk∞ := max |xi | .
1≤i≤d

In particular, the `2 norm is the familiar Euclidean norm, and it is by far the best studied in this
context. We write SVPp and CVPp for the respective problems in the `p norm. CVP is known to
be at least as hard as SVP (in any norm, under an efficient reduction that preserves the rank and
approximation factor) [GMSS99] and appears to be strictly harder.
Starting with the breakthrough work of Lenstra, Lenstra, and Lovász in 1982 [LLL82], algorithms
for solving these problems in both their exact and approximate forms have found innumerable
applications, including factoring polynomials over the rationals [LLL82], integer programming [Len83,
Kan87, DPV11], cryptanalysis [Sha84, Odl90, JS98, NS01], etc. More recently, many cryptographic
primitives have been constructed whose security is based on the worst-case hardness of these or
closely related lattice problems [Ajt04, Reg09, GPV08, Pei08, Pei16]. Given the obvious importance
of these problems, their complexity is quite well studied. Below, we survey some of these results.
We focus on algorithms for the exact and near-exact problems since these are most relevant to
our work and because the best known algorithms for the approximate variants of these problems
typically use algorithms for the exact problems as subroutines [Sch87, GN08, MW16]. (Many of the
results described below are also summarized in Table 1.)

1.1

Algorithms for SVP and CVP

The current fastest known algorithms for solving
The AKS algorithm and its descendants.
SVPp all use the celebrated randomized sieving technique due to Ajtai, Kumar, and Sivakumar [AKS01]. The original algorithm from [AKS01] was the first 2O(n) -time algorithm for SVP, and
it worked for both p = 2 and p = ∞.
In the p = 2 case, a sequence of works improved upon the constant in the exponent [NV08,
PS09, MV10, LWXZ11], and the current fastest running time of an algorithm that provably solves
SVP2 exactly is 2n+o(n) [ADRS15].1 While progress has slowed, this seems unlikely to be the end
of the story. Indeed, there are heuristic sieving algorithms that run in time (3/2)n/2+o(n) [NV08,
1

The algorithm in [ADRS15] is quite a bit different than the other algorithms in this class, but it can still be
thought of as a sieving algorithm.

1

WLTB11, Laa15, BDGL16], and there is some reason to believe that the provably correct [ADRS15]
algorithm can be improved. In particular, there is a provably correct 2n/2+o(n) -time algorithm that
approximates SVP2 up to a small constant approximation factor [ADRS15].
A different line of work extended the randomized sieving approach of [AKS01] to obtain 2O(n) time algorithms for SVP in additional norms. In particular, Blömer and Naewe extended it to all `p
norms [BN09]. Subsequent work extended this further, first to arbitrary symmetric norms [AJ08]
and then to the “near-symmetric norms” that arise in integer programming [Dad12].
Finally, a third line of work extended the [AKS01] approach to approximate CVP. Ajtai, Kumar,
and Sivakumar themselves showed a 2O(n) -time algorithm for approximating CVP2 to within any
constant approximation factor strictly greater than one [AKS02]. Blömer and Naewe obtained the
same result for all `p norms [BN09], and Dadush extended it further to arbitrary symmetric norms
and again to “near-symmetric norms” [Dad12]. We stress, however, that none of these results apply
to exact CVP, and indeed, there are some barriers to extending these algorithms to exact CVP.
(See, e.g., [ADS15].)
Exact CVP appears to be a much more subtle problem than
Exact algorithms for CVP.
2
exact SVP. Indeed, progress on exact CVP has been much slower than the progress on exact SVP.
Over a decade after [AKS01], Micciancio and Voulgaris presented the first 2O(n) -time algorithm
for exact CVP2 [MV13], using elegant new techniques built upon the approach of Sommer, Feder,
and Shalvi [SFS09]. Specifically, they achieved a running time of 4n+o(n) , and subsequent work
even showed a running time of 2n+o(n) for CVP2 with Preprocessing (in which the algorithm
is allowed access to arbitrary advice that depends on the lattice but not the target vector; see
Section 2.1) [BD15]. Later, [ADS15] showed a 2n+o(n) -time algorithm for CVP2 , so that the current
best known asymptotic running time is actually the same for SVP2 and CVP2 .
However, for p =
6 2, progress for exact CVPp has been minimal. Indeed, the fastest known
algorithms for exact CVPp with p 6= 2 are still the nO(n) -time enumeration algorithms first developed
by Kannan in 1987 [Kan87, DPV11, MW15]. Both algorithms for exact CVP2 mentioned in the
previous paragraph use many special properties of the `2 norm, and it seems that substantial new
ideas would be required to extend them to arbitrary `p norms.

1.2

Hardness of SVP and CVP

Van Emde Boas showed the NP-hardness of CVPp for any p and SVP∞ in 1981 [vEB81]. Extending
this to SVPp for finite p was a major open problem until it was proven (via a randomized reduction)
for all 1 ≤ p ≤ ∞ by Ajtai in 1998 [Ajt98]. There has since been much follow-up work, showing the
hardness of these problems for progressively larger approximation factors, culminating in NP-hardness
of approximating CVPp up to a factor of nc/ log log n for some constant c > 0 [ABSS93, DKRS03]
and hardness of SVPp with the same approximation factor under plausible complexity-theoretic
assumptions [CN98, Mic01b, Kho05, HR12]. These results are nearly the best possible under
√
plausible assumptions, since approximating either problem up to a factor of n is known to be in
NP ∩ coNP [GG00, AR05, Pei08].
2

In particular, there can be arbitrarily many lattice points that are approximate closest vectors, which makes
sieving techniques seemingly useless for solving exact CVP. (See, e.g., [ADS15] for a discussion of this issue.) We
note, however, that hardness results (including ours) tend to produce CVP instances with a bounded number of
approximate closest vectors (e.g., 2O(n) ).

2

However, such results only rule out the possibility of polynomial-time algorithms (under reasonable complexity-theoretic assumptions). They say very little about the quantitative hardness of
these problems for a fixed lattice rank n.3
This state of affairs is quite frustrating for two reasons. First, in the specific case of CVP2 ,
algorithmic progress has reached an apparent barrier. In particular, both known techniques for
solving exact CVP2 in singly exponential time are fundamentally unable to produce algorithms whose
running time is asymptotically better than the current best of 2n+o(n) [MV13, ADS15].4 Second,
some lattice-based cryptographic constructions are close to deployment [ADPS16, BCD+ 16, NIS16].
In order to be practically secure, these constructions require the quantitative hardness of certain
lattice problems, and so their designers rely on quantitative hardness assumptions [APS15]. If, for
example, there existed a 2n/20 -time algorithm for SVPp or CVPp , then these cryptographic schemes
would be insecure in practice.
We therefore move in a different direction. Rather than trying to extend non-quantitative
hardness results to larger approximation factors, we show quantitative hardness results for exact (or
nearly exact) problems. To do this, we use the tools of fine-grained complexity.

1.3

Fine-grained complexity

Impagliazzo and Paturi [IP99] introduced the Exponential Time Hypothesis (ETH) and the Strong
Exponential Time Hypothesis (SETH) to help understand the precise hardness of k-SAT. Informally,
ETH asserts that 3-SAT takes 2Ω(n) -time to solve in the worst case, and SETH asserts that k-SAT
takes essentially 2n -time to solve for unbounded k. I.e., SETH asserts that brute-force search is
essentially optimal for solving k-SAT for large k.
Recently, the study of fine-grained complexity has leveraged ETH, SETH, and several other assumptions to prove quantitative hardness results about a wide range of problems. These include both
problems in P (see, e.g., [CLR+ 14, BI15, ABW15] and the survey by Vassilevska Williams [Wil15]),
and NP-hard problems (see, e.g., [PW10, CDL+ 12, CFK+ 15]). Although these results are all
conditional, they help to explain why making further algorithmic progress on these problems is
difficult—and suggest that it might be impossible. Namely, any non-trivial algorithmic improvement
would disprove a very well-studied hypothesis.
One proves quantitative hardness results using fine-grained reductions (see [Wil15] for a formal
definition). For example, there is an efficient mapping from k-SAT formulas on n variables to
Hitting Set instances with universes of n elements [CDL+ 12]. This reduction is fine-grained in the
sense that for any constant ε > 0, a 2(1−ε)n -time algorithm for Hitting Set implies a 2(1−ε)n -time
algorithm for k-SAT, breaking SETH.
Despite extensive effort, no faster-than-2n -time algorithm for k-SAT with unbounded k has
been found. Nevertheless, there is no consensus on whether SETH is true or not, and recently,
Williams [Wil16] refuted a very strong variant of SETH. This makes it desirable to base quantitative
hardness results on weaker assumptions when possible, and indeed our main result holds even
3

One can derive certain quantitative hardness results from known hardness proofs, but in most cases the resulting
lower bounds are quite weak. The only true quantitative hardness results known prior to this work were a folklore
ETH-hardness result for CVP and an unpublished result due to Samuel Yeom, showing that CVP cannot be solved in
−4
time 210 n under plausible complexity-theoretic assumptions [Vai15]. (In Section 6.2, we present a similar proof of a
stronger statement.)
4
Both techniques require short vectors in each of the 2n cosets of L mod 2L (though for apparently different
reasons).

3

Problem

Upper Bound

CVPp
CVP2
CVP∞ /SVP∞
CVPPp

nO(n) (2O(n) )
2n
O(n)
2
O(n)
n
(2O(n) )

SETH
2n
—
2n *
—

Lower Bounds
Max-2-SAT ETH
2ωn/3
2Ω(n)
2ωn/3
2Ω(n)
—
2Ω(n)
√
√
2Ω( n)
2Ω( n)

Notes
Gap-ETH
2Ω(n) *
2Ω(n) *
2Ω(n) *
—

“almost all” p ∈
/ 2Z

Table 1: Summary of known quantitative upper and lower bounds, with new results in blue. Upper
bounds in parentheses hold for any constant approximation factor strictly greater than one, and
lower bounds with a ∗ apply for some constant approximation factor strictly greater than one. ω is
the matrix multiplication exponent, satisfying 2 ≤ ω < 2.373. We have suppressed smaller factors.

assuming a weaker variant of SETH based on the hardness of Weighted Max-k-SAT (except for the
case of p = ∞).

1.4

Our contribution

We now enumerate our results. See also Table 1.
SETH-hardness of CVPp .
Our main result is the SETH-hardness of CVPp for any odd integer
p ≥ 1 and p = ∞ (and SVP∞ ). Formally, we prove the following. (See Sections 3 and 4 for finite p
and Section 6.3 for p = ∞.)
Theorem 1.1. For any constant integer k ≥ 2 and any odd integer p ≥ 1 or p = ∞, there is an
efficient reduction from k-SAT with n variables and m clauses to CVPp (or SVP∞ ) on a lattice of
rank n (with ambient dimension n + O(m)).
In particular, there is no 2(1−ε)n -time algorithm for CVPp for any odd integer p ≥ 1 or p = ∞
(or SVP∞ ) and any constant ε > 0 unless SETH is false.
Unfortunately, we are unable to extend this result to even integers p, and in particular, to the
important special case of p = 2. In fact, this is inherent, as we show that our approach necessarily
fails for even integers p ≤ k − 1. In spite of this, we actually prove the following result that
generalizes Theorem 1.1 to “almost all” p ≥ 1 (including non-integer p).
Theorem 1.2. For any constant integer k ≥ 2, there is an efficient reduction from k-SAT with n
variables and m clauses to CVPp on a lattice of rank n (with ambient dimension n + O(m)) for any
p ≥ 1 such that
1. p is an odd integer or p = ∞;
2. p ∈
/ Sk , where Sk is some finite set (containing all even integers p ≤ k − 1); or
3. p = p0 + δ(n) for any p0 ≥ 1 and any δ(n) 6= 0 that converges to zero as n → ∞.
In particular, if SETH holds then for any constant ε > 0, there is no 2(1−ε)n -time algorithm for
CVPp for any p ≥ 1 such that
1. p is an odd integer or p = ∞;
4

2. p ∈
/ Sk for some sufficiently large k (depending on ε); or
3. p = p0 + δ(n).
Notice that this lower bound (Theorem 1.2) comes tantalizingly close to resolving the quantitative
complexity of CVP2 . In particular, we obtain a 2n -time lower bound on CVP2+δ for any 0 6= δ(n) =
o(1), and the fastest algorithm for CVP2 run in time 2n+o(n) . But, formally, Theorems 1.1 and 1.2
say nothing about CVP2 . (Indeed, there is at least some reason to believe that CVP2 is easier than
CVPp for p 6= 2 [RR06].)
We note that our reductions actually work for Weighted Max-k-SAT for all finite p =
6 ∞, so
that our hardness result holds under a weaker assumption than SETH, namely, the corresponding
hypothesis for Weighted Max-k-SAT.
Finally, we note that in the special case of p = ∞, our reduction works even for approximate
CVP∞ , or even approximate SVP∞ , with an approximation factor of γ := 1 + 2/(k − 1). In
particular, γ is constant for fixed k. This implies that for every constant ε > 0, there is a constant
γε > 1 such that no 2(1−ε)n -time algorithm approximates SVP∞ or CVP∞ to within a factor of γε
unless SETH fails.
As we discussed above, many 2O(n) -time
Quantitative hardness of approximate CVP.
algorithms for CVPp only work for γ-approximate CVPp for constant approximation factors γ > 1.
However, the reduction described above only works for exact CVPp (except when p = ∞).5
So, it would be preferable to show hardness for some constant approximation factor γ > 1. One
way to show such a hardness result is via a fine-grained reduction from the problem of approximating
Max-k-SAT to within a constant factor. Indeed, in the k = 2 case, we show that such a reduction
exists, so that there is no 2o(n) -time algorithm for approximating CVPp to within some constant
factor unless a 2o(n) -time algorithm exists for approximating Max-2-SAT. We also note that a
2o(n) -time algorithm for approximating Max-2-SAT to within a constant factor would imply one for
Max-3-SAT as well. (See Proposition 2.12.)
We present this result informally here (without worrying about specific parameters and the
exact definition of approximate Max-2-SAT). See Section 5 for the formal statement.
Theorem 1.3. There is an efficient reduction from approximating Max-2-SAT with n variables
and m clauses to within a constant factor to approximating CVPp to within a constant factor on a
lattice of rank n (with ambient dimension n + O(m)) for any finite p ≥ 1.
Quantitative hardness of CVP with Preprocessing.
CVP with Preprocessing (CVPP) is
the variant of CVP in which we are allowed arbitrary advice that depends on the lattice, but
not the target vector. CVPP and its variants have potential applications in both cryptography
(e.g., [GPV08]) and cryptanalysis. And, an algorithm for CVPP2 is used as a subroutine in the
celebrated Micciancio-Voulgaris algorithm for CVP2 [MV13, BD15]. The complexity of CVPPp is
well studied, with both hardness of approximation results [Mic01a, FM04, Reg04, AKKV11, KPV14],
and efficient approximation algorithms [AR05, DRS14].
We prove the following quantitative hardness result for CVPPp . (See Section 6.1.)
5

One can likely show that our “exact” reductions actually work for γ-approximate CVPp with some approximation
factor γ = 1 + o(1). But, this is not very interesting because standard techniques for “boosting” the approximation
factor are useless for us. (They increase the rank far too much.)

5

√

Theorem 1.4. For any 1 ≤ p < ∞, there is no 2o( n) -time algorithm for CVPP unless there is a
(non-uniform) 2o(n) -time algorithm for Max-2-SAT. In particular, no such algorithm exists unless
(non-uniform) ETH fails.
Additional quantitative hardness results for CVPp .
We also observe the following weaker
hardness result for CVPp for any 1 ≤ p < ∞ based on different assumptions. The ETH-hardness
of CVPp was already known in folklore, and even written down by Samuel Yeom in unpublished
work [Vai15]. We present a slightly stronger theorem than what was previously known, showing a
reduction from Max-2-SAT on n variables to CVPp on a lattice of rank n. (Prior to this work, we
were only aware of reductions from 3-SAT on n variables to CVPp on a lattice of rank Cn for some
very large constant C > 1000.)
Theorem 1.5. For any 1 ≤ p < ∞, there is an efficient reduction from Max-2-SAT with n variables
to CVPp on a lattice of rank n (and dimension n + m, where m is the number of clauses).
In particular, for any constant c > 0, there is no (poly(n) · 2cn )-time algorithm for CVPp unless
there is a 2cn -time algorithm for Max-2-SAT, and there is no 2o(n) -time algorithm for CVPp unless
ETH fails.
The fastest known algorithm for the Max-2-SAT problem is the poly(n) · 2ωn/3 -time algorithm
due to Williams [Wil05], where 2 ≤ ω < 2.373 is the matrix multiplication exponent [Wil12, LG14].
This implies that a faster than 2ωn/3 -time algorithm for CVPp (and CVP2 in particular) would
yield a faster algorithm for Max-2-SAT. (See, e.g., [Woe08] Open Problem 4.7 and the preceding
discussion.)

1.5

Techniques

Max-2-SAT.
We first show a straightforward reduction from Max-2-SAT to CVPp for any
1 ≤ p < ∞. I.e., we prove Theorem 1.5. This simple reduction will introduce some of the high-level
ideas needed for our more difficult reductions.
Given a Max-2-SAT instance Φ with n variables and m clauses, we construct the lattice basis
B :=

Φ̄
2αIn

!

,

(1)

where α > 0 is some very large number and Φ̄ ∈ Rm×n is given by
Φ̄i,j :=





2
−2

 0

if the ith clause contains xj ,
if the ith clause contains ¬xj ,
otherwise .

(2)

I.e., the rows of Φ̄ correspond to clauses and the columns correspond to variables. Each entry
encodes whether the relevant variable is included in the relevant clause unnegated, negated, or not
at all, using 2, −2, and 0 respectively. (We assume without loss of generality that no clause contains
repeated literals or a literal and its negation simultaneously.) The target t ∈ Rm+n is given by
t := (t1 , t2 , . . . , tm , α, α, . . . , α)T ,

(3)

ti := 3 − 2ηi ,

(4)

where

6

where ηi is the number of negated variables in the ith clause.
Notice that the copy of 2αIn at the bottom of B together with the sequence of α’s in the last
coordinates of t guarantee that any lattice vector Bz with z ∈ Zn is at distance at least αn1/p away
from t. Furthermore, if z ∈
/ {0, 1}n , then this distance increases to at least α(n − 1 + 3p )1/p . This is
a standard gadget, which will allow us to ignore the case z ∈
/ {0, 1}n (as long as α is large enough).
I.e., we can view z as an assignment to the n variables of Φ.
Now, suppose z does not satisfy the ith clause. Then, notice that the ith coordinate of Bz will
be exactly −2ηi , so that (Bz − t)i = 0 − 3 = −3. If, on the other hand, exactly one literal in the ith
clause is satisfied, then the ith coordinate of Bz will be 2−2ηi , so that (Bz−t)i = 2−3 = −1. Finally,
if both literals are satisfied, then the ith coordinate will be 4 − 2ηi , so that (Bz − t)i = 4 − 3 = 1.
In particular, if the ith clause is not satisfied, then |(Bz − t)i | = 3. Otherwise, |(Bz − t)i | = 1.
It follows that the distance to the target is exactly distp (t, L)p = αp n + S + 3p (m − S) =
p
α n − (3p − 1)S + 3p m, where S is the maximal number of satisfied clauses of Φ. So, the distance
distp (t, L) tells us exactly the maximum number of satisfiable clauses, which is what we needed.
Difficulties extending this to k-SAT. The above reduction relied on one very important fact:
that |4 − 3| = |2 − 3| < |0 − 3|. In particular, a 2-SAT clause can be satisfied in two different ways;
either one variable is satisfied or two variables are satisfied. We designed our CVP instance above so
that the ith coordinate of Bz − t is 4 − 3 if two literals in the ith clause are satisfied by z ∈ {0, 1}n ,
2 − 3 if one literal is satisfied, and 0 − 3 if the clause is unsatisfied. Since |4 − 3| = |2 − 3|, the
“contribution” of this ith coordinate to the distance kBz − tkpp is the same for any satisfied clause.
Since |0 − 3| > |4 − 3|, the contribution to the ith coordinate is larger for unsatisfied clauses than
satisfied clauses.
Suppose we tried the same construction for a k-SAT instance. I.e., suppose we take Φ̄ ∈ Rm×n
to encode the literals in each clause as in Eq. (2) and construct our lattice basis B as in Eq. (1) and
target t as in Eq. (3), perhaps with the number 3 in the definition of t replaced by an arbitrary
t∗ ∈ R. Then, the ith coordinate of Bz − t would be 2Si − t∗ , where Si is the number of literals
satisfied in the ith clause.
No matter how cleverly we choose t∗ ∈ R, some satisfied clauses will contribute more to the
distance than others as long as k ≥ 3. I.e., there will always be some “imbalance” in this contribution.
As a result, we will not be able to distinguish between, e.g., an assignment that satisfies all clauses
but has Si far from t∗ /2 for all i and an assignment that satisfies fewer clauses but has Si ≈ t∗ /2
whenever i corresponds to a satisfying clause.
In short, for k ≥ 3, we run into trouble because satisfying assignments to a clause may satisfy
anywhere between 1 and k literals, but k distinct numbers obviously cannot all be equidistant from
some number t∗ . (See Section 6.2 for a simple way to get around this issue by adding to the rank
of the lattice. Below, we show a more technical way to do this without adding to the rank of the
lattice, which allows us to prove SETH-hardness.)
A solution via isolating parallelepipeds.
To get around the issue described above for k ≥ 3,
we first observe that, while many distinct numbers cannot all be equidistant from some number t∗ ,
∗
∗
it is trivial to find many distinct vectors in Rd that are equidistant from some vector t∗ ∈ Rd .
We therefore consider modifying the reduction from above by replacing the scalar ±2 values in our
∗
∗
matrix Φ̄ with vectors in Rd for some d∗ . In particular, for some vectors V = (v 1 , . . . , v k ) ∈ Rd ×k ,

7

we define Φ̄ ∈ Rd

∗ m×n

as

Φ̄i,j





vs
−v s
:=

 0
d

if xj is the sth literal in the ith clause,
if ¬xj is the sth literal in the ith clause,
otherwise ,

(5)

where we have abused notation and taken Φ̄i,j to be a column vector in d∗ dimensions. By defining
∗
t ∈ Rd m+n appropriately,6 we will get that the “contribution of the ith clause to the distance”
∗
kBz − tkpp is exactly kV y − t∗ kpp for some t∗ ∈ Rd , where y ∈ {0, 1}k such that ys = 1 if and only
if z satisfies the sth literal of the relevant clause. (See Table 2 for a diagram showing the output of
the reduction and Theorem 3.2 for the formal statement.) We stress that, while we have increased
the ambient dimension by nearly a factor of d∗ , the rank of the lattice is still n.
This motivates the introduction of our primary technical tool, which we call isolating paral∗
lelepipeds. For 1 ≤ p ≤ ∞, a (p, k)-isolating parallelepiped is represented by a matrix V ∈ Rd ×k and
∗
a shift vector t∗ ∈ Rd with the special property that one vertex of the parallelepiped V {0, 1}k − t∗ is
“isolated.” (Here, V {0, 1}k − t∗ is an affine transformation of the hypercube, i.e., a parallelepiped.) In
particular, every vertex of the parallelepiped, V y − t∗ for y ∈ {0, 1}k has unit length kV y − t∗ kp = 1
except for the vertex −t∗ , which is longer, i.e., kt∗ kp > 1. (See Figure 1.)
In terms of the reduction above, an isolating parallelepiped is exactly what we need. In particular,
if we plug V and t∗ into the above reduction, then all satisfied clauses (which correspond to non-zero
y in the above description) will “contribute” 1 to the distance kBz − tkpp , while unsatisfied clauses
(which correspond to y = 0) will contribute 1 + δ for some δ > 0. Therefore, the total distance will
be exactly kBz − tkpp = αp n + m+ (z) + (m − m+ (z))(1 + δ) = αp n − δm+ (z) + (1 + δ)m, where
m+ (z) is the number of clauses satisfied by z. So, the distance distp (t, L) exactly corresponds to
the maximal number of satisfied clauses, as needed.
Constructing isolating parallelepipeds.
Of course, in order for the above to be useful, we
must show how to construct these (p, k)-isolating parallelepipeds. Indeed, it is not hard to find
constructions for all p ≥ 1 when k = 2, and even for all k in the special case when p = 1 (see
Figure 1). Some other fairly nice examples can also be found for small k, as shown in Figure 2.
For p > 1 and large k, these objects seem to be much harder to find. (In fact, in Section 4.2, we
show that there is no (p, k)-isolating parallelepiped for any even integer p ≤ k − 1.) Our solution is
therefore a bit technical.
k
k
At a high level, in Section 4, we consider a natural class of parallelepipeds V ∈ R2 ×k , t∗ ∈ R2
parametrized by some weights α0 , α1 , . . . , αk ≥ 0 and a scalar shift t∗ ∈ R. These parallelepipeds
are constructed so that the length of the vertex kV y − t∗ kpp for y ∈ {0, 1}k depends only on
the Hamming weight of y and is linear in the αi for fixed t∗ . In other words, there is a matrix
Mk (p, t∗ ) ∈ R(k+1)×(k+1) such that Mk (p, t∗ )(α0 , . . . , αk )T encodes the value of kV y − t∗ kpp for each
possible Hamming weight of y ∈ {0, 1}k . (See Lemma 4.2.)
We show that, in order to find weights α0 , . . . , αk ≥ 0 such that V and t∗ define a (p, k)-isolating
parallelepiped, it suffices to find a t∗ such that Mk (p, t∗ ) is invertible. For each odd integer p ≥ 1
and each k ≥ 2, we show an algorithm that finds such a t∗ . (See Section 4.1.)
6

In particular, we replace the scalars ti in Eq. (4) with vectors
ti := t∗ −

X

∗

v s ∈ Rd ,

where the sum is over s such that the sth literal in the ith clause is negated.

8

(k, k)

v2

v1 + v2

(2, 2)

t∗

··

·

(1, 1)

t∗

(0, 0)
0

v1

Figure 1: (p, k)-isolating parallelepipeds for p = 2, k = 2 (left) and p = 1, k ≥ 1 (right). On the left,
the vectors v 1 , v 2 , and v 1 + v 2 are all at the same distance from t∗ , while 0 is strictly farther away.
On the right is the degenerate parallelepiped generated by k copies of the vector (1, 1). The vectors
(i, i) are all at the same `1 distance from t∗ for 1 ≤ i ≤ m, while (0, 0) is strictly farther away. The
(scaled) unit balls centered at t∗ are shown in red, while the parallelepipeds are shown in black.







1
V :=
·

1/3
2 · 12









121/3 121/3 121/3

1
1
−1 

1
−1
1 

1
−1
−1 
,
−1
1
1 


−1
1
−1 
−1
−1
1

t∗ :=

1
2 · 121/3



2 · 121/3


2 




2 


·
2 

 .

2 




2 

2

Figure 2: A (3, 3)-isolating parallelepiped in seven dimensions. One can verify that kV y − t∗ k33 = 1
for all non-zero y ∈ {0, 1}3 , and kt∗ k33 = 3/2.

9

To extend this result to other p ≥ 1, we consider the determinant of Mk (p, t∗ ) for fixed k and t∗ ,
viewed as a function of p. We observe that this function has a rather nice form—it is a Dirichlet
P
polynomial. I.e., for fixed t∗ and k, the determinant can be written as exp(ai p) for some ai ∈ R.
Such a function has finitely many roots unless it is identically zero. So, we take the value of t∗ from
above such that, say, Mk (1, t∗ ) is invertible. Since Mk (1, t∗ ) does not have zero determinant, the
Dirichlet polynomial corresponding to det(Mk (p, t∗ )) cannot be identically zero and therefore has
finitely many roots. This is how we prove Theorem 1.2. (See Section 4.3.)
Extension to constant-factor approximation.
In order to extend our hardness results to
approximate CVPp for finite p, we can try simply using the same reduction with k-SAT replaced by
approximate Max-k-SAT. Unfortunately, this does not quite work. Indeed, it is easy to see that the
“identity matrix gadget” that we use to restrict our attention to lattice vectors whose coordinates
are in {0, 1} (Eq. (1)) cannot tolerate an approximation factor larger than 1 + O(1/n) (for finite p).
However, we observe that when k = 2, this identity matrix gadget is actually unnecessary. In
particular, even without this gadget, it “never helps” to consider a lattice vector whose coordinates
are not all in {0, 1}. It then follows immediately from the analysis above that Gap-2-SAT reduces
to approximate CVPp with a constant approximation factor strictly greater than one. We note that
we do not know how to extend this result to larger k > 2 (except when p = 1, see Theorem 5.3). We
show that the case k = 2 is sufficient for proving Gap-ETH-hardness (see Proposition 2.12), but we
suspect that one can just “remove the identity matrix gadget” from all of our reductions for finite p.
If this were true, it would show Gap-ETH-hardness of approximation for slightly larger constant
approximation factors and imply even stronger hardness results under less common assumptions.

1.6

Open questions

The most important question that we leave open is the extension of our SETH-hardness result
to arbitrary p ≥ 1. In particular, while our result applies to p = p(n) 6= 2 that approaches 2
asymptotically, it does not apply to the specific case p = 2. An extension to p = 2 would settle
the time complexity of CVP2 up to a factor of 2o(n) (assuming SETH). However, we know that
our technique does not work in this case (in that (2, k)-parallelepipeds do not exist for k ≥ 3), so
substantial new ideas might be needed to resolve this issue.
Another direction would be to strengthen our hardness of approximation results in one of two
possible directions. First, one could try to increase the approximation factor. (Prior techniques for
amplifying the approximation factor increase the rank of the lattice quite a bit, so they do not yield
very interesting quantitative hardness results.) Second, one could try to show a reduction from
Gap-k-SAT to approximate CVPp for k ≥ 3. For p ∈ {1, ∞}, we already have such a reduction, and
as we mentioned above, we suspect that we can simply “remove the identity matrix gadget” in our
current reduction to achieve this for 1 < p < ∞. But, we do not know how to prove that this works.
Finally, we note that our main reduction constructs lattices of rank n, but the ambient dimension
d can be significantly larger. (Specifically, d = n + O(m), where m is the number of clauses in the
relevant SAT instance, and where the hidden constant depends on k and can be very large.) Lattice
problems are typically parameterized in terms of the rank of the lattice (and for the `2 norm, one
can assume without loss of generality that d = n), but it is still interesting to ask whether we can
reduce the ambient dimension d.

10

Organization
In Section 2, we review some necessary background knowledge. In Section 3, we show how to
use a (p, k)-isolating parallelepiped (for finite p) to reduce any n-variable instance of k-SAT to a
CVPp instance with rank n, and we show that this immediately gives SETH-hardness for p = 1.
In Section 4, we show how to construct (p, k)-isolating parallelepipeds, first for odd integers p ≥ 1
and then for “almost all” p. In Section 5, we show 2Ω(n) -hardness of approximating √
CVPp up to a
Ω(
n) ETH- and
constant factor. In Section 6, we prove a number of additional hardness results: 2
Max-2-SAT-hardness of CVPPp (Section 6.1), ETH- and Max-2-SAT-hardness of CVPp (Section 6.2),
and SETH-hardness of CVP∞ and SVP∞ (Section 6.3).

2

Preliminaries

Throughout this paper, we work with lattice problems over Rd for convenience. Formally, we must
pick a suitable representation of real numbers and consider both the size of the representation
and the efficiency of arithmetic operations in the given representation. But, we omit such details
throughout to ease readability.

2.1

Computational lattice problems

Let distp (L, t) := minx∈L kx − tkp denote the `p distance of t to L. In addition to SVP and CVP,
we also consider a variant of CVP called the Closest Vector Problem with Preprocessing (CVPP),
which allows arbitrary preprocessing of a lattice.
Definition 2.1. For any γ ≥ 1 and 1 ≤ p ≤ ∞, the γ-approximate Shortest Vector Problem
with respect to the `p norm (γ-SVPp ) is the promise problem defined as follows. Given a lattice L
(specified by a basis B ∈ Rd×n ) and a number r > 0, distinguish between a ‘YES’ instance where
there exists a non-zero vector v ∈ L such that kvkp ≤ r, and a ‘NO’ instance where kvkp > γr for
all non-zero v ∈ L.
Definition 2.2. For any γ ≥ 1 and 1 ≤ p ≤ ∞, the γ-approximate Closest Vector Problem with
respect to the `p norm (γ-CVPp ) is the promise problem defined as follows. Given a lattice L
(specified by a basis B ∈ Rd×n ), a target vector t ∈ Rd , and a number r > 0, distinguish between a
‘YES’ instance where distp (L, t) ≤ r, and a ‘NO’ instance where distp (L, t) > γr.
When γ = 1, we refer to the problems simply as SVPp and CVPp , respectively.
Definition 2.3. The Closest Vector Problem with Preprocessing with respect to the `p norm (CVPPp )
is the problem of finding a preprocessing function P and an algorithm Q which work as follows.
Given a lattice L (specified by a basis B ∈ Rd×n ), P outputs a new description of L. Given P (L), a
target vector t ∈ Rd , and a number r > 0, Q decides whether distp (L, t) ≤ r.
When we measure the running time of a CVPP algorithm, we only count the running time of Q,
and not of the preprocessing algorithm P .

11

2.2

Satisfiability problems and the Max-Cut problem

A k-SAT formula Φ on n Boolean variables x1 , . . . , xn and m clauses C1 , . . . , Cm is a conjunction
k
Φ = ∧m
i=1 Ci of clauses Ci = ∨s=1 `i,s , where the literals `i,s denote a variable xj or its negation ¬xj .
The goal is to decide whether there exists an assignment a ∈ {0, 1}n to the variables of Φ such that
all clauses have at least one “true” literal, i.e., so that all clauses are satisfied.
The value of a k-SAT formula Φ, denoted val(Φ), is the maximum fraction of clauses satisfied
by an assignment to Φ.
Definition 2.4. Given a k-SAT formula Φ and constants 0 ≤ δ < ε ≤ 1, the (δ, ε)-Gap-k-SAT
problem is the promise problem defined as follows. The goal is to distinguish between a ‘YES’
instance in which val(Φ) ≥ ε, and a ‘NO’ instance in which val(Φ) < δ.
Definition 2.5. Given a k-SAT formula Φ with clauses C = {C1 , . . . , Cm }, a clause weight function
w : C → Z+ , and a weight threshold W , the Weighted Max-k-SAT problem is to decide whether there
P
exists an assignment a to the variables of Φ such that Ci is sat. by a w(Ci ) ≥ W .
Definition 2.6. Given an undirected graph G = (V, E), an edge weight function w : E → Z+ , and
a weight threshold W , the Weighted Max-CUT problem is defined as follows. The goal is to decide
P
whether V can be partitioned into sets V1 and V2 such that eij ∈E:vi ∈V1 ,vj ∈V2 w(eij ) ≥ W .
There exists a folklore reduction from an instance of Weighted Max-Cut on a graph with n
vertices to an instance of Weighted Max 2-SAT on a formula with n variables. See, e.g., [GHNR03].

2.3

Exponential Time Hypotheses

Impagliazzo and Paturi [IP99] introduced the following two hypotheses (ETH and SETH), which
are now widely used to study the quantitative hardness of computational problems.
Definition 2.7. The Exponential Time Hypothesis (ETH) is the hypothesis defined as follows. For
every k ≥ 3 there exists a constant ε > 0 such that no algorithm solves k-SAT formulas with n
variables in 2εn -time. In particular, there is no 2o(n) -time algorithm for 3-SAT.
Definition 2.8. The Strong Exponential Time Hypothesis (SETH) is the hypothesis defined as
follows. For every constant ε > 0 there exists k such that no algorithm solves k-SAT formulas with
n variables in 2(1−ε)n -time.
An important tool in the study of the exact complexity of k-SAT is the Sparisification Lemma of
Impagliazzo, Paturi, and Zane [IPZ01] which roughly says that any k-SAT formula can be replaced
with 2εn formulas each with O(n) clauses for some ε > 0.
Proposition 2.9 (Sparsification Lemma, [IPZ01]). For every k ∈ Z+ and ε > 0 there exists a
constant c = c(k, ε) such that any k-SAT formula Φ with n variables can be expressed as Φ = ∨ri=1 Ψi
where r ≤ 2εn and each Ψi is a k-SAT formula with at most cn clauses. Moreover, this disjunction
can be computed in 2εn -time.
In this paper we also consider the W-Max-SAT-SETH hypothesis, which corresponds to SETH
but with Weighted Max-k-SAT in place of k-SAT. Our main result only relies on this weaker variant
of SETH, and is therefore more robust.
Dinur [Din16] and Manurangsi and Raghavendra [MR17] recently introduced a “gap” version of
ETH, which asserts that Gap-3-SAT takes 2Ω(n) -time.
12

Definition 2.10. The (randomized) Gap-Exponential Time Hypothesis ((randomized) Gap-ETH)
is the hypothesis that there exist constants δ < 1 and ε > 0 such that no (randomized) algorithm
solves (δ, 1)-Gap-3-SAT instances with n variables in 2εn -time.
As Dinur [Din16] notes, one can sparsify a Gap-SAT instance simply by sampling clauses.
Therefore, we can assume (almost) without loss of generality that Gap-ETH applies only to formulas
with O(n) clauses. The caveat is that the sampling is randomized, so finding a 2o(n) -time algorithm
for sparse Gap-3-SAT only implies a randomized 2o(n) -time algorithm for general Gap-3-SAT.
We give a variant of Dinur’s sampling argument in Proposition 2.11. The idea is to show that
both the total number of sampled clauses and the number of sampled clauses that are satisfied by
any given assignment are highly concentrated around their expectation by using the Chernoff bound,
and then to take a union bound over the bad events where these quantities deviate substantially
from their expectation.
We will use the following multiplicative Chernoff bounds (see, e.g., [HP]). Let X1 , . . . , Xn be
independent identically distributed Bernoulli random variables with expectation p, so that the
P
expectation of ni=1 Xi is µ = pn. Then:
Pr[

n
X

2 /2

Xi < (1 − α)µ] < e−µα

,

(6)

.

(7)

i=1

Pr[

n
X

2 /4

Xi > (1 + α)µ] < e−µα

i=1

Proposition 2.11 (Sparsification for Gap-SAT). For any 0 < δ < δ 0 < 1, there is a polynomial-time
randomized reduction from a (δ, 1)-Gap-k-SAT instance Φ with n variables and m clauses to a
(δ 0 , 1)-Gap-k-SAT instance Φ0 with n variables and O(n) clauses.
Proof. Let Φ0 be the formula obtained by sampling each clause of Φ independently with probability
p := min{1, 10/(δα2 ) · n/m}, where α is fixed so that −(1 − δ 0 /δ)/(1 + δ 0 /δ) < α < 1. Clearly, if
val(Φ) = 1 then val(Φ0 ) = 1 as well. We analyze the case where val(Φ) < δ.
In expectation Φ0 has pm clauses. Furthermore, because val(Φ0 ) < δ, in expectation any fixed
assignment will satisfy fewer than δpm clauses of Φ0 . Therefore by Equation (6),
Pr[Number of clauses in Φ0 ≤ (1 − α)pm] ≤ e−α

2 pm/2

≤ e−2n .

(8)

Furthermore, by Equation (7), we have that for each fixed assignment a,
Pr[Number of clauses in Φ0 sat. by a ≥ (1 + α)δpm] ≤ e−α

2 δpm/4

≤ e−2n .

(9)

By applying Equations (8) and (9), and taking a union bound we get that the probability that
has at least (1 − α)pm clauses and that no assignment to Φ0 satisfies more than (1 + α)δpm
clauses is at least 1 − (e−2n + 2n e−2n ) ≥ 1 − 2e−n . Therefore,

Φ0

val(Φ0 ) ≤

(1 + α)pm
· δ < δ0
(1 − α)pm

with high probability.

13

x1

x2

···

xn−1

xn

v1

v2

···

0d∗

−v 3

t∗ − v 3

..
.

···

..

..
.

..
.

..
.

0d∗

−v 1

···

v2

v3

t∗ − v 1

x1
x2
..
.

2α1/p
0
..
.

0
2α1/p
..
.

···
···
..
.

0
0
..
.

0
0
..
.

α1/p
α1/p
..
.

xn−1
xn

0
0

0
0

···
···

2α1/p
0

0
2α1/p

α1/p
α1/p

(

C1
..
.

.

(

Cm

B

t

Table 2: A basis B and target vector t output by the reduction from Theorem 3.2 with some
∗
∗
(p, 3)-isolating parallelepiped given by V = (v 1 , v 2 , v 3 ) ∈ Rd ×3 and t∗ ∈ Rd . In this example, the
first clause is C1 ≡ x1 ∨ x2 ∨ ¬xn and the mth clause is Cm ≡ ¬x2 ∨ xn−1 ∨ xn . By the definition of
an isolating parallelepiped (Definition 3.1), the contribution of the first d coordinates to the distance
kBz − tkpp will be 1 for any assignment z ∈ {0, 1}n satisfying C1 , while non-satisfying assignments
contribute (1 + δ) for some δ > 0. For example, if z1 = 1, z2 = 0, zn = 1, the clause C1 is satisfied,
and the first d coordinates will contribute kv 1 − v 3 − (t∗ − v 3 )kpp = kv 1 − t∗ kpp = 1. On the other
hand, if z1 = 0, z2 = 0, zn = 1, then C1 is not satisfied, and k − v 3 − (t∗ − v 3 )kpp = kt∗ kpp = 1 + δ.
Additionally, we will use a reduction of Garey et al. [GJS76] from 3-SAT to Max-2-SAT which
also works as a reduction from Gap-3-SAT to Gap-2-SAT. The reduction works by outputting ten 1and 2-clauses for each 3-clause in the original formula. Any assignment which satisfies the original
clause corresponds to an assignment which satisfies 7 of the output clauses, and any assignment
which does not satisfy the original clause corresponds to an assignment which satisfies 6 of the
output clauses.
Proposition 2.12 ([GJS76, Theorem 1.1]). For every 0 ≤ δ < ε ≤ 1, there is a polynomial-time
reduction from every instance of (δ, ε)-Gap-3-SAT with n variables and m clauses to an instance of
((6 + δ)/10, (6 + ε)/10)-Gap-2-SAT with n + m variables and 10m clauses.

3

SETH-hardness from isolating parallelepipeds

We start by giving a reduction from instances of weighted Max-k-SAT on formulas with n variables
to instances of CVPp with rank n for all p that uses a certain geometric object, which we define
next. Let 1n and 0n denote the all 1s and all 0s vectors of length n respectively, and let In denote
the n × n identity matrix.

14

∗

∗

Definition 3.1. For any 1 ≤ p ≤ ∞ and integer k ≥ 2, we say that V ∈ Rd ×k and t∗ ∈ Rd define
a (p, k)-isolating parallelepiped if ktkp > 1 and kV x − t∗ kp = 1 for all x ∈ {0, 1}k \ {0k }.
In order to give the reduction, we first introduce some notation related to SAT. Let Φ be a
k-SAT formula on n variables x1 , . . . , xn and m clauses C1 , . . . , Cm . Let ind(`) denote the index of
the variable underlying a literal `. I.e., ind(`) = j if ` = xj or ` = ¬xj . Call a literal ` positive if
` = xj and negative if ` = ¬xj for some variable xj . Given a clause Ci = ∨ks=1 `i,s , let Pi := {s ∈ [k] :
`i,s is positive} and let Ni := {s ∈ [k] : `i,s is negative} denote the indices of positive and negative
literals in Ci respectively. Given an assignment a ∈ {0, 1}n to the variables of Φ, let Si (a) denote the
indices of literals in Ci satisfied by a. I.e., Si (a) := {s ∈ Pi : aind(`i,s ) = 1} ∪ {s ∈ Ni : aind(`i,s ) = 0}.
Finally, let m+ (a) denote the number of clauses of Φ satisfied by the assignment a, i.e., the number
of clauses i for which |Si (a)| ≥ 1.
Theorem 3.2. If there exists a computable (p, k)-isolating parallelepiped for some p = p(n) ∈ [1, ∞)
and integer k ≥ 2, then there exists a polynomial-time reduction from any (weighted-)Max-k-SAT
instance with n variables to a CVPp instance of rank n.
Proof. For simplicity, we give a reduction from unweighted Max-k-SAT, and afterwards sketch how
to modify our reduction to handle the weighted case as well. Namely, we give a reduction from any
Max-k-SAT instance (Φ, W ) to an instance (B, t∗ , r) of CVPp . Here, the formula Φ is on n variables
x1 , . . . , xn and m clauses C1 , . . . , Cm . (Φ, W ) is a ‘YES’ instance if there exists an assignment a
such that m+ (a) ≥ W .
∗
By assumption, there exist computable d∗ = d∗ (p, k) ∈ Z+ , V = [v 1 , . . . , v k ] ∈ Rd ×k , and
∗
t∗ ∈ Rd such that kt∗ kp = (1 + δ)1/p for some δ > 0 and kV z − t∗ kp = 1 for all z ∈ {0, 1}k \ {0k }.
We define the output CVPp instance as follows. Let d := md∗ + n. The basis B ∈ Rd×n and
target vector t ∈ Rd in the output instance have the form


B1
..
.




B=



∗

Bm
2α1/p · In







,






t=



t1
..
.
tm
α1/p · 1n




,



∗

with blocks Bi ∈ Rd ×n and ti ∈ Rd for 1 ≤ i ≤ m and α := m + (m − W )δ. Note that α is the
maximum possible contribution of the clauses C1 , . . . , Cm to kBy − tkpp when (Φ, W ) is a ‘YES’
instance. For every 1 ≤ i ≤ m and 1 ≤ j ≤ n, set the jth column (Bi )j of block Bi (corresponding
to the clause Ci = ∨ks=1 `i,s ) as
(Bi )j :=





v s if xj is the sth literal of clause i,
−v s if ¬xj is the sth literal of clause i,

 0 ∗ otherwise,
d

and set ti := t∗ − s∈Ni v s . Set r := (α(n + 1))1/p .
Clearly, the reduction runs in polynomial time. We next analyze for which y ∈ Zn it holds that
kBy − tkp ≤ r. Given y ∈
/ {0, 1}n ,
P

kBy − tkpp ≥ k2α1/p In y − α1/p 1n kpp ≥ α(n + 2) > rp ,

15

so we only need to analyze the case when y ∈ {0, 1}n . Consider an assignment y ∈ {0, 1}n to the
variables of Φ. Then,
kBi y − ti kp =

X

yind(`i,s ) · v s −

s∈Pi

=

X



yind(`i,s ) · v s − t∗ −

s∈Ni

yind(`i,s ) · v s +

s∈Pi

=

X
X

X

s∈Si (a)



s∈Ni

1 − yind(`i,s ) · v s − t∗

p



p

s∈Ni

X

vs

v s − t∗ .
p

By assumption, the last quantity is equal to 1 if |Si (y)| ≥ 1, and is equal to (1 + δ)1/p otherwise.
Because |Si (y)| ≥ 1 if and only if Ci is satisfied, it follows that
kBy − tkpp =

m
X



kBi y − ti kpp + αn = m + (m − m+ (y))δ + αn .

i=1

Therefore, kBy − tkp ≤ r if and only if m+ (y) ≥ W , and therefore there exists y such that
kBy − tkp ≤ r if and only if (Φ, W ) is a ‘YES’ instance of Max-k-SAT, as needed.
To extend this to a reduction from weighted Max-k-SAT to CVPp , simply multiply each block
Bi and the corresponding target vector ti by w(Ci )1/p , where w(Ci ) denotes the weight of the clause
Ci . Then, by adjusting α to depend on the weights w(Ci ) we obtain the desire reduction.
Because the rank n of the output CVPp instance matches the number of variables in the input
SAT formula, we immediately get the following corollary.
Corollary 3.3. For any efficiently computable p = p(n) ∈ [1, ∞) if there exists a computable
(p, k)-isolating parallelepiped for infinitely many k ∈ Z+ , then, for every constant ε > 0 there
is no 2(1−ε)n -time algorithm for CVPp assuming W-Max-SAT-SETH. In particular there is no
2(1−ε)n -time algorithm for CVPp assuming SETH.
It is easy to construct a (degenerate) family of isolating parallelepipeds for p = 1, and therefore
we get hardness of CVP1 as a simple corollary. (See Figure 1.)
Corollary 3.4. For every constant ε > 0 there is no 2(1−ε)n -time algorithm for CVP1 assuming
W-Max-SAT-SETH, and in particular there is no 2(1−ε)n -time algorithm for CVP1 assuming SETH.
1
Proof. Let k ∈ Z+ , let V = [v 1 , . . . , v k ] with v 1 = · · · = v k := k−1
(1, 1)T ∈ R2 , and let t∗ :=
1
T
2
∗
k
∗
k−1 (k, 1) ∈ R . Then, kV x − t k1 = 1 for every x ∈ {0, 1} \ {0k }, and kt k1 = (k + 1)/(k − 1) > 1.
The result follows by Corollary 3.3.

4

Finding isolating parallelepipeds
∗

∗

We now show how to find a (p, k)-isolating parallelepiped given by V ∈ Rd ×k and t∗ ∈ Rd as in
Definition 3.1. We will first show a general strategy for trying to find such an object for any p ≥ 1
and integer k ≥ 2. In Section 4.1, we will show how to successfully implement this strategy in the
case when p is an odd integer. In Section 4.2, we show that (p, k)-isolating parallelepipeds do not
16

exist for even integers p ≤ k − 1. Finally, in Section 4.3 we show how to mostly get around this
issue in order to find (p, k)-isolating parallelepipeds for “almost all” p ≥ 1.
It will actually be convenient to find a slightly different object that “works with {±1}k instead
of {0, 1}k .” We observe below that this suffices.
∗

Lemma 4.1. There is an efficient algorithm that takes as input a matrix V ∈ Rd ×k and vector
∗
t∗ ∈ Rd such that kV y − t∗ kp = 1 for any y ∈ {±1}k \ {−1k } and k − V 1k − t∗ kp > 1 , and outputs
∗
∗
a matrix V 0 ∈ Rd ×k and vector (t∗ )0 ∈ Rd that form a (p, k)-isolating parallelepiped.
Proof. Define V 0 := 2V and (t∗ )0 = V 1k + t∗ . Now consider the affine transformation f : Rk → Rk
defined by f (x) := (2x − 1k ), which maps {0, 1}k to {±1}k and 0k to −1k . Then, for x ∈ {0, 1}k
and y = f (x) = 2x − 1k ∈ {±1}k , we have
kV 0 x − (t∗ )0 kp = V 0

y + 1k
− (t∗ )0
2

p

= V0

y
1k
+V0
− (t∗ )0
2
2

p

= kV y − t∗ kp ,

as needed.
Intuitively, a “reasonable” matrix V should act symmetrically on bit strings. I.e., if y, y 0 ∈ {±1}k
have the same number of positive entries, then V y should be a permutation of V y 0 . This implies
that any row of V must be accompanied by all possible permutations of this row. If we further
require that each row in V is α · v for some v ∈ {±1}k and α ∈ R, then we arrive at a very general
construction that is still possible to analyze.
k
For weights α0 , . . . , αk ≥ 0, we define V := V (α0 , . . . , αk ) ∈ R2 ×k as follows. The rows of V
1/p
are indexed by the strings {±1}k , and row v is αk−|v| v T , where
|v| := {# of positive entries in v}
k

is the number of positive entries in v. For a shift t∗ ∈ R, we set t∗ := t∗ (α0 , . . . , αk , t∗ ) ∈ R2
1/p
such that the coordinate of t∗ corresponding to v is αk−|v| t∗ . (Figure 2 is an example of this
construction. In particular, it shows V (α0 , α1 , α2 , α3 ) with α0 = 12, α1 = α2 = 1 and α3 = 0 and
t∗ (α0 , α1 , α2 , α3 , t∗ ) with t∗ = 2, where we have omitted the last row, whose weight is zero.)
In what follows, we will use the binomial coefficient ji extensively, and we adopt the convention
that

i
j

= 0 if j > i or j < 0 or j ∈
/ Z.

Lemma 4.2. For any y ∈ {±1}k , weights α0 , . . . , αk ≥ 0, and shift t∗ ∈ R,
kV y −

t∗ kpp

=

k
X
j=0

αk−j

k
X
|y|
`=0

`

!

!

k − |y|
· 2|y| + 2j − k − 4` − t∗
j−`

k

p

,

where V := V (α0 , . . . , αk ) ∈ R2 ×k and t∗ := t∗ (α0 , . . . , αk , t∗ ) as above.
In other words, kV y − t∗ kpp depends only on |y|, and if w ∈ (R≥0 )k+1 is the vector such that
wj = kV y 0 − t∗ kpp for all y 0 ∈ {±1} with |y 0 | = j, then



w = Mk (p, t ) 


∗

17

α0
α1
..
.
αk




 ,



where Mk (p, t∗ ) ∈ R(k+1)×(k+1) is given by
Mk (p, t∗ )i,j :=

k
X
`=0

i
`

!

!

k−i
· 2i + 2j − k − 4` − t∗
j−`

p

.

(10)

Proof. We have
kV y − t∗ kpp =

k
X

X

αj

j=0

hv, yi − t∗

p

.

|v|=k−j

Notice that hv, yi depends only on how many of the j negative entries of v align with the positive
entries of y. In particular,
∗ p

X

hv, yi − t

=

|v|=k−j

!
!
k
X
|y| k − |y|
`=0

j−`

`

k
X
|y|

!

=

`=0

`

· − ` + (|y| − `) + (j − `) − (k − |y| − j + `) − t∗

!

k − |y|
· 2|y| + 2j − k − 4` − t∗
j−`

p

p

,

as needed.
Lemma 4.3. For any t∗ ∈ R, the matrix Mk (p, t∗ ) defined in Eq. (10) is stochastic.
Mk (p, t∗ )1k+1 = λ(t∗ )1k+1 for some λ(t∗ ) ∈ R. Furthermore, λ(t∗ ) > 0.

I.e.,

Proof. We rearrange the sum corresponding to the ith entry of Mk (p, t∗ )1k+1 , setting r := (i+j)/2−`
to obtain
k X
k
X
j=0 `=0

i
`

!

!

k−i
· 2i + 2j − k − 4` − t∗
j−`

p

=

X

|4r − k − t∗ |p

r

=

X

k
X
j=0

∗ p

|4r − k − t |

r

k
X
j=0

i
(i + j)/2 − r

!

k−i
r + (j − i)/2

!

i
r + (i − j)/2

!

k−i
r + (j − i)/2

!

Finally, we recall Vandermonde’s identity, which says that
k
X
j=0

i
r + (i − j)/2

!

k−i
r + (j − i)/2

!

=

k
r

!

.

Therefore, the summation does not depend on i (and is clearly positive), as needed.
Lemma 4.3 tells us that for any t∗ ∈ R, Mk (p, t∗ )(1k+1 )/λ = 1k+1 for some λ > 0. We wish
to show that, for some t∗ ∈ R, we can find α0 , . . . , αk ≥ 0 such that Mk (p, t∗ )(α0 , α1 , . . . , αk )T =
1k+1 + εe0 for some ε > 0, where e0 := (1, 0, . . . , 0)T . In order to do this, it suffices to show that
Mk (p, t∗ ) is invertible. Then, we can take
(α0 , α1 , . . . , αk )T := 1k+1 /λ + εMk (p, t∗ )−1 e0 .
If ε := (λ · kMk (p, t∗ )−1 e0 k∞ )−1 > 0, then the αi must be non-negative. We make this formal in
the next proposition.
18

.

Proposition 4.4. There is an efficient algorithm that takes as input any p ≥ 1, an integer k ≥ 2,
and t∗ ∈ R such that det(Mk (p, t∗ )) 6= 0, where Mk (p, t∗ ) is defined as in Eq. (10) and outputs
k
k
V ∈ R2 ×k and t∗ ∈ R2 that define a (p, k)-isolating parallelepiped.
Proof. By Lemma 4.1, it suffices to construct a matrix that works for y ∈ {±1}k . The algorithm
behaves as follows on input k ≥ 2 and p ≥ 1 and t∗ ∈ R. By Lemma 4.3, Mk (p, t∗ )1k+1 = λ1k+1 for
some λ > 0. Since we are promised that det(Mk (p, t∗ )) 6= 0, we see that Mk (p, t∗ ) is invertible. The
algorithm therefore sets
(α0 , . . . , αk )T := 1k+1 /λ + εMk (p, t∗ )−1 e0 ,

(11)

where ε := (λ · kMk (p, t∗ )−1 e0 k∞ )−1 > 0 is chosen to be small enough such that the αi are all
non-negative. Finally, it outputs V := V (α0 , . . . , αk ) and t∗ := t∗ (α0 , . . . , αk , t∗ ) as defined above.
To prove correctness, we note that V and t∗ have the desired property. Indeed, it follows
from the definition of Mk (p, t∗ ) in Lemma 4.2 that kV y − t∗ kpp is the jth coordinate of w :=
Mk (p, t∗ )(α0 , . . . , αk )T , where j := |y|. But, by Eq. (11), we see that the jth coordinate of w is
1 + ε if j = 0 and is 1 otherwise, as needed.

4.1

Finishing the proof for odd integer p

We now handle the case when p ≥ 1 is an odd integer. Notice that, if p ≥ 1 is an integer, then
det(Mk (p, t∗ )) is some piecewise combination of polynomials of degree at most (k + 1)p in t∗ . In
particular, it is a polynomial in t∗ if we restrict our attention to the interval t∗ ∈ [−k, −k + 2].
We wish to argue that this is not the zero polynomial when p is odd. To prove this, it suffices to
show that the coefficient of (t∗ )(k+1)p is non-zero, which we do below by studying a matrix whose
determinant is this coefficient (when p is odd).
We first show an easy claim concerning matrices that can be written as sums of the identity
plus a certain kind of rank-one matrix.
Claim 4.5. For any matrix A ∈ Rd×d with constant columns given by Ai,j = aj for some
a0 , . . . , ad−1 ∈ R and any λ ∈ R,
det(A − λId ) = (−λ)d−1

X



aj − λ .

j

P

Proof. Notice that A is a rank-one stochastic matrix with one non-zero eigenvalue given by aj .
P
Therefore, the characteristic polynomial of A is det(A − λId ) = (−λ)d−1 ( aj − λ), as needed.
Lemma 4.6. For an integer k ≥ 1 and an odd integer p ≥ 1, the function t∗ 7→ det(Mk (p, t∗ )),
where Mk (p, t∗ ) is defined as in Eq. (10), is a polynomial of degree at most (k + 1)p when restricted
to the interval t∗ ∈ [−k, −k + 2]. Furthermore, the coefficient of (t∗ )(k+1)p of this polynomial is
exactly 2k (2 − 2k ).
In particular, t∗ 7→ det(Mk (p, t∗ )) is a non-zero polynomial of degree (k + 1)p on the interval
t∗ ∈ [−k, −k + 2] for k ≥ 2.
Proof. For any t∗ ∈ [−k, −k + 2], the matrix Mk (p, t∗ ) is given by
∗

Mk (p, t )i,j =

k
X
`=0

!

i
`

!

k−i
· 2i+2j−k−4`−t∗
j−`

p

19

=

k
X
`=0

!

δi+j−2`

i
`

!

k−i
·(2i+2j−k−4`−t∗ )p ,
j−`

where δr = −1 if r = 0 and 1 otherwise. (Here, we have used the fact that `i k−i
j−` is only non-zero
∗
when ` ≤ min(i, j). Therefore, 2i + 2j ≥ 4`, so that 2i + 2j − k − 4` − t ≥ 2i + 2j − 4` − 2 ≥ 0
unless 2i − 2j − 4` = 0.)
The coefficient of (t∗ )(k+1)p in the polynomial t∗ 7→ det(Mk (p, t∗ )) is therefore given by det(M 0 ),
where M 0 is defined as


0

(M )i,j := −

k
X

!

δ2`−i−j

`=0

!

k−i
j−`

!

k
X
k−i
i
−
(j − i)/2
`
`=0

!

k−i
k
−
(j − i)/2
j

i
=2
(i + j)/2
i
=2
(i − j)/2

i
`



!

!

!

!

k−i
j−`

!

,

where we have again applied Vandermonde’s identity. Notice that the first term is non-zero if and

only if i = j, in which case it is equal to 2. In other words, M 0 = A + 2Ik+1 , where Ai,j := − kj .
The result then follows from Claim 4.5.
Corollary 4.7. There is an efficient algorithm that takes as input an integer k ≥ 2 and odd integer
p ≥ 1 and outputs t∗ ∈ Q such that det(Mk (p, t∗ )) 6= 0, with Mk (p, t∗ ) defined as in Eq. (10).
Proof. The algorithm works as follows. It chooses (k + 1)p + 1 distinct points t0 , . . . , t(k+1)p ∈
[−k, −k + 2] arbitrarily. (E.g., it chooses ti = −k + 2i/((k + 1)p).) For each ti , it computes
det(Mk (p, ti )). It outputs the first ti such that the determinant is non-zero.
We claim that det(Mk (p, ti )) 6= 0 for at least one index i. Indeed, by Lemma 4.6, t∗ 7→
det(Mk (p, t∗ )) is a non-zero polynomial of degree (k + 1)p. The result then follows from the fact
that such a polynomial can have at most (k + 1)p roots.
Theorem 1.1 for finite p now follows immediately from Theorems 3.2 together with Proposition 4.4,
and Corollary 4.7.

4.2

Limitations of the approach

In the previous section, we showed that for every odd p ≥ 1 and every integer k ≥ 2, there exists a
(p, k)-isolating parallelepiped. This allowed us to conclude that CVPp is SETH-hard for odd values
of p. Now, we show that this approach necessarily fails for even p ≥ 2. Namely, we show that for
every even p, there is no (p, k)-isolating parallelepiped for any k > p.7 For simplicity, we show this
for p = 2, but a straightforward generalization works for all even p.
∗

Lemma 4.8. For any integer k ≥ 3 and vectors v 1 , . . . , v k , t∗ ∈ Rd , we have
X

(−1)|S| t∗ −

i∈S

S⊆[k]
7

X

2

vi

2

=0.

When k ≤ p, it is possible to construct (p, k)-isolating parallelepiped for even p. See, e.g., Figure 1.

20

Proof. We have
X
S⊆[k]

|S|

(−1)

∗

t −

X
i∈S

2

vi

2

=

|S|

X

kt∗ k22

(−1)

D

∗

−2 t ,

= kt∗ k22 ·

(−1)|S| − 2

X
S⊆[k]

X

vi +

kt∗ k22

X

·

X

(−1)

|S|

t∗ , v i ·

·0−2

2

vi

X

!

2

(−1)|S|

S3i

+2

X

hv i , v j i ·

i<j

S3i

X

X
i∈S

i∈[k]

kvi k22

i∈[k]

=

E

i∈S

S⊆[k]

+

X

X

(−1)|S|

S3i,j

∗

ht , v i i · 0

i∈[k]

+

X

kvi k22 · 0 + 2

X

hv i , v j i · 0

i<j

i∈[k]

=0,
where the penultimate equality uses the fact that
X

(−1)|S| = (1 − 1)n = 0

S⊆[n]

for n ≥ 1.
Corollary 4.9. There is no (2, k)-isolating parallelepiped for any integer k ≥ 3.
∗

Proof. Assume V = [v 1 , . . . , v k ] ∈ Rd ×k and t∗ ∈ Rd form a (2, k)-isolating parallelepiped. For
P
any S 6= ∅, kt∗ − i∈S v i k22 = 1 by the definition of an isolating parallelepiped. Thus, applying
Lemma 4.8, we have
kt∗ k22 =

X

(−1)|S|+1 t∗ −

X
i∈S

∅6=S⊆[k]

2

vi

2

=1,

which contradicts the assumption that V and t∗ form an isolating parallelepiped.

4.3

Extending our result to almost all p

We now wish to extend Theorem 1.1 to arbitrary p ≥ 1. Unfortunately, we know that we cannot
do this for all p, since we showed in Section 4.2 that no such construction is possible when p is an
even integer. However, we show a construction that works for “almost all values of p.” In particular,
for any fixed k, the construction works for all but finitely many choices of p. We also observe that
this implies that, for every fixed p0 , k, there is an ε > 0 such that the construction works for every
p ∈ (p0 − ε) or p ∈ (p0 + ε). In particular, for any non-zero δ = δ(n) = o(1), the construction works
for p = p0 + δ(n) for sufficiently large integers n.
In Section 4.1, we observed that the function t∗ 7→ det(Mk (p, t∗ )) is a piecewise polynomial when
p is an integer. This is what allowed us to analyze this case relatively easily (in both Section 4.1 and
in Section 4.2). For non-integer p, the function t∗ 7→ det(Mk (p, t∗ )) is much less nice. So, instead of
holding p fixed and varying t∗ , we will be interested in studying the function fk,t∗ (p) := det(Mk (p, t∗ ))
for fixed t∗ and k. We first observe that this function has a fairly nice structure.

21

Lemma 4.10. For any t∗ ∈ R, integer k ≥ 1, and p ≥ 1, let
fk,t∗ (p) := det(Mk (p, t∗ )) ,

(12)

where Mk (p, t∗ ) is as defined in Eq. (10). Then, for fixed k, t∗ , fk,t∗ (p) is a Dirichlet polynomial.
I.e., there are some real numbers b0 , . . . , br , c0 , . . . , cr ∈ R (depending on t∗ and k) such that
fk,t∗ (p) =

r
X

bi exp(ci p)

(13)

i=0

for some finite r.
Proof. To see that fk,t∗ (p) is a Dirichlet polynomial for fixed t∗ , k, it suffices to note that (1) each
entry of Mk (p, t∗ ) is a Dirichlet polynomial; (2) the determinant of a matrix can be written as a
polynomial in the coordinates; and (3) a polynomial of Dirichlet polynomials is itself a Dirichlet
polynomial.
Corollary 4.11. There is an efficient algorithm that takes as input k ≥ 2 and any p ≥ 1 and either
k
k
fails or outputs V ∈ R2 ×k and t∗ ∈ R2 that define a (p, k)-isolating parallelepiped. Furthermore,
for any fixed k ≥ 2, the algorithm only fails for finitely many choices of p ≥ 1.
Proof. By Corollary 4.7, for any k ≥ 2, we can find a t∗ ∈ Q such that, say, fk,t∗ (1) 6= 0, where
fk,t∗ (p) is defined as in Eq. (12). Clearly, fk,t∗ (p) is non-zero as a function of p for these values
of t∗ , k. Furthermore, by Lemma 4.10, fk,t∗ (p) is a Dirichlet polynomial. The result follows by
the fact that any non-zero Dirichlet polynomial has finitely many roots (see, e.g., Theorem 3.1
in [Jam06]).
Theorem 4.12. There is an efficient algorithm that takes as input an integer k ≥ 2 and any p ≥ 1
k
k
and either fails or outputs V ∈ R2 ×k and t∗ ∈ R2 that define a (p, k)-isolating parallelepiped.
Furthermore, for any fixed k ≥ 2, the algorithm only fails on finitely many values of p ≥ 1.8
Proof. The result follows immediately from Proposition 4.4 and Corollary 4.11.
Item 2 of Theorem 1.2 now follows immediately from Theorem 3.2 and Theorem 4.12.
We now provide what amounts to a different interpretation of the above.
Lemma 4.13. There is an efficient algorithm that takes as input any p0 ≥ 1 and an integer k ≥ 2
and outputs a value t∗ such that fk,t∗ (p0 + δ) and fk,t∗ (p0 − δ) are non-zero for sufficiently small
δ > 0, where fk,t∗ (p) is as defined in Eq. (12).
Proof. The algorithm simply calls the procedure from Corollary 4.7 with, say, p = 1 and outputs
the result. I.e., it suffices to choose any t∗ such that fk,t∗ (1) 6= 0. As in the proof of Corollary 4.11,
we observe that the function fk,t∗ (p) is zero on a finite set of values X. The result then follows by
taking δ := minx∈X\{p0 } |x − p0 |/2 if X \ {p0 } is non-empty, and δ := c for any c > 0 otherwise.
Finally, we derive the main theorem of this section.
8

As we observed in Section 4.2, the set of failure points necessarily includes all even integers p ≤ k − 1.

22

Theorem 4.14. For any efficiently computable δ(n) 6= 0 that converges to zero as n → ∞ and p0 ≥ 1,
there is an efficient algorithm that takes as input an integer k ≥ 2 and sufficiently large positive
k
k
integer n and outputs a matrix V ∈ R2 ×k and vector t∗ ∈ R2 that define a (p0 + δ(n), k)-isolating
parallelepiped.
Proof. The result follows immediately from Proposition 4.4 and Lemma 4.13. In particular, the
algorithm runs the procedure from Lemma 4.13, receiving as output some t∗ ∈ R such that
fk,t∗ (p0 ± ε) is non-zero for sufficiently small ε > 0. In particular, if n is sufficiently large, then
fk,t∗ (p0 + δ(n)) will be non-zero. The result then follows from Proposition 4.4.
Item 3 of Theorem 1.2 now follows from Theorem 3.2 and Theorem 4.14.

5

Gap-ETH-based Hardness of Approximation

In this section we prove Gap-ETH-based hardness of approximation for CVPp for every p ∈ [1, ∞).
We also show a stronger hardness of approximation result for CVP1 . (In Section 6.3, we additionally
show a stronger result for p = ∞.) The main idea behind our proof is to use the reduction from
Max-2-SAT to CVP described in Section 1.5 without the “identity matrix gadget” that we used
to force any closest vector to be a 0-1 combination of basis vectors. We will show that this is
permissible because the resulting CVP instance always has a 0-1 combination of basis vectors that
is at least as close to the target as any other lattice vector.
Theorem 5.1. For every 0 ≤ δ < ε ≤ 1 and every p ∈ [1, ∞), there is a polynomial-time reduction
from any (δ, ε)-Gap-2-SAT instance with n variables to an instance of γ-CVPp of rank n, where


γ :=

δ + (1 − δ) · 3p
ε + (1 − ε) · 3p

1/p

>1.

In particular, when ε = 1, the corresponding approximation factor is (δ + (1 − δ) · 3p )1/p .
Proof. Given a (δ, ε)-Gap-2-SAT instance with n variables x1 , . . . , xn and m clauses C1 , . . . , Cm , we
construct a CVPp instance (B, t, r) for some fixed p ∈ [1, ∞) as follows. Let B ∈ Zm×n be the basis
defined by


 2 if Ci contains xj ,
−2 if Ci contains ¬xj ,
bi,j :=

 0 otherwise.
Let t ∈ Rm be the target vector defined by ti := 3 − 2|Ni |, and let r := (εm + (1 − ε)m · 3p )1/p .
We claim that there is always a 0-1 combination of basis vectors which is a closest vector to t.
Assuming this claim, we analyze kBy − tkp only for y ∈ {0, 1}n without loss of generality, while
deferring the proof of the claim until the end.
Let y ∈ {0, 1}n be an assignment to the variables of Φ. For every 1 ≤ i ≤ m,
|(By − t)i | = 2

X

= 2

X

yind(`i,s ) −

s∈Pi

X



yind(`i,s ) − (3 − 2|Ni |)

s∈Ni

yind(`i,s ) +

s∈Pi

X
s∈Ni

= 2 · |Si (y)| − 3 .
23



(1 − yind(`i,s ) ) − 3

(14)

The last expression is equal to 1 if y satisfies Ci (i.e. if |Si (y)| ≥ 1) and 3 if not. We therefore have
kBy −

tkpp

=

m
X

|(By − t)i |p = m+ (y) + (m − m+ (y)) · 3p .

i=1

Therefore, if val(Φ) ≥ ε then there exists y ∈ {0, 1}n such that kBy − tkpp ≤ εm + (1 − ε)m · 3p = rp ,
and if val(Φ) < δ, then for every y ∈ {0, 1}n , it holds that kBy − tkpp > δm + (1 − δ)m · 3p = γ p rp .
It follows that the reduction achieves the claimed approximation factor of γ.
It remains to prove the claim that there is always a 0-1 combination of basis vectors which is a
closest vector to t. We show this by demonstrating that for every y ∈ Zn there exists χ(y) ∈ {0, 1}n
such that kB · χ(y) − tkp ≤ kBy − tkp . Given y ∈ Zn , let χ(y) ∈ {0, 1}n denote the vector whose
ith coordinate is set to 1 if yi ≥ 1 and is set to 0 otherwise.
Fix y ∈ Zn and 1 ≤ i ≤ n, and refer to Equation (14). If χ(y) satisfies Ci then |(By − t)i | ≥
|(B·χ(y)−t)i | = 1. On the other hand, if χ(y) does not satisify Ci , then yind(`i,s ) ≤ 0 for all s ∈ Pi and
1 − yind(`i,s ) ≤ 0 for all s ∈ Ni so that |(By − t)i | ≥ 3 and therefore |(By − t)i | ≥ |(B · χ(y) − t)i | = 3.
Combining these cases it follows that for all y ∈ Zn and 1 ≤ i ≤ n, |(B · χ(y) − t)i | ≤ |(By − t)i |,
and therefore kB · χ(y) − tkp ≤ kBy − tkp , proving the claim.
Corollary 5.2. For every p ∈ [1, ∞) and 0 < δ < δ 0 < 1, there is no 2o(n) -time algorithm for
γ-CVPp with


6 + δ 0 + (4 − δ 0 ) · 3p 1/p
γ :=
>1
7 + 3p+1
unless randomized Gap-ETH (with respect to (δ, 1)-Gap-3-SAT) fails.
Proof. Concatenate the reductions described in Proposition 2.11, Proposition 2.12, and Theorem 5.1.9

5.1

A stronger result for `1

In Theorem 5.1 we showed that there was no need to use the identity matrix gadget in our reduction
from Gap-2-SAT to CVP. An interesting question is whether the identity matrix gadget is also
unnecessary in our reduction in Theorem 3.2 from Gap-k-SAT to CVPp using (p, k)-isolating
parallelepipeds. If so, then we get stronger “Gap-SETH-hardness” for CVPp for all p for which
there exist (p, k)-isolating parallelepipeds for infinitely many k ∈ Z+ .
Although we do not know how to show this in general, we are able to get stronger hardness of
approximation for CVP1 in this way by using the family of (1, k)-isolating parallelepipeds described
in Corollary 3.4. The analysis is similar to the analysis in Theorem 5.1. In particular, a 0-1
combination of basis vectors will always be at least as close to the target vector as any other lattice
vector will.
Theorem 5.3. For every 0 ≤ δ < ε ≤ 1, there is a polynomial-time reduction from any (δ, ε)-Gapk-SAT instance with n variables to an instance of γ-CVP1 of rank n, where
γ :=

 δ · (k − 1) + (1 − δ) · (k + 1) 

ε · (k − 1) + (1 − ε) · (k + 1)

9

> 1.

Note that the Gap-2-SAT instance output by Proposition 2.12 contains 1-clauses as well as 2-clauses. We therefore
stress that the reduction described in Theorem 5.1 works for this case as well.

24

Proof. Given a (δ, ε)-Gap-k-SAT instance with n variables x1 , . . . , xn and m clauses C1 , . . . , Cm , we
construct a CVP1 instance (B, t, r) as follows. The basis B ∈ Z(2m)×n and target vector t ∈ Z2m in
the output instance have the form
B1
 .. 
B =  . ,
Bm


t1
 .. 
t =  . ,
tm







with blocks Bi ∈ Z2×n and ti ∈ Z2 for 1 ≤ i ≤ m. For every 1 ≤ i ≤ m and 1 ≤ j ≤ n, set the jth
column (Bi )j of block Bi (corresponding to the clause Ci = ∨ks=1 `i,s ) as




(1, 1)T
−(1, 1)T
(Bi )j :=

 (0, 0)T

if Ci contains xj ,
if Ci contains ¬xj ,
otherwise,

and set ti := (k, 1)T − |Ni | · (1, 1)T . Set r := εm(k − 1) + (1 − ε) · m(k + 1).
We claim that there is always a 0-1 combination of basis vectors that is closest to t. Assuming
the claim, we analyze kBy − tk only for y ∈ {0, 1}n without loss of generality, while deferring the
proof of the claim until the end.
Let y ∈ {0, 1}n be an assignment to the variables of Φ. For every 1 ≤ i ≤ m,

kBi y − ti k1 =
=

X

yind(`i,s ) · (1, 1)T −

X

s∈Pi

s∈Ni

X

X

yind(`i,s ) · (1, 1)T +

s∈Pi



yind(`i,s ) · (1, 1)T − (k, 1)T − |Ni | · (1, 1)T
1 − yind(`i,s ) · (1, 1)T − (k, 1)T


s∈Ni

= |Si (y)| · (1, 1)T − (k, 1)T

1

1


1

(15)

.

The last expression is equal to k − 1 if y satisfies Ci (i.e. if |Si (y)| ≥ 1) and k + 1 if not. We
therefore have
kBy − tk1 =

m
X

kBi y − ti k1 = m+ (y) · (k − 1) + (m − m+ (y)) · (k + 1).

i=1

Therefore, if val(Φ) ≥ ε then there exists y ∈ {0, 1}n such that kBy − tk1 ≤ εm(k − 1) + (1 −
ε) · m(k + 1) = r, and if val(Φ) < δ then for every y ∈ {0, 1}n , it holds that kBy − tk1 >
δm(k − 1) + (1 − δ)m(k + 1) = γr. It follows that the reduction achieves the claimed approximation
factor of γ.
It remains to prove the claim that there is always a 0-1 combination of basis vectors that is a
closest vector to t. We show this by demonstrating that for every y ∈ Zn there exists χ(y) ∈ {0, 1}n
such that kBχ(y) − tk1 ≤ kBy − tk1 . Given y ∈ Zn , let χ(y) ∈ {0, 1}n denote the vector whose
coordinate is set to 1 if yi ≥ 1 and is set to 0 otherwise.
Note that kc(1, 1)T − (k, 1)T k1 = k − 1 for all c ∈ [k], and kc(1, 1)T − (k, 1)T k1 ≥ k + 1 for
all c ∈ Z \ [k]. Fix y ∈ Zn and 1 ≤ i ≤ n, and refer to Equation (15). If χ(y) satisfies Ci
then kBi · y − ti k1 ≥ kBi · χ(y) − ti k1 = k − 1. On the other hand, if χ(y) does not satisfy
Ci , then yind(`i,s ) ≤ 0 for all s ∈ Pi and 1 − yind(`i,s ) ≤ 0 for all s ∈ Ni so that kBi · y − ti k1 ≥
25

kBi · χ(y) − ti k1 = k + 1. Combining these cases it follows that for all y ∈ Zn and 1 ≤ i ≤ n,
kBi · χ(y) − ti k1 ≤ kBi · y − ti k1 , and therefore kB · χ(y) − tk1 ≤ kBy − tk1 , proving the claim.

6

Additional hardness results

In this section we prove a number of additional results about the quantitative hardness of CVP and
related problems. In Section 6.1, we give a reduction from Max-2-SAT to CVPPp for all p ∈ [1, ∞),
proving Theorem 1.4. In Section 6.2, we give a reduction from Max-k-SAT (and in particular
Max-2-SAT) to CVPp for all p ∈ [1, ∞), proving Theorem 1.5. Finally, in Section 6.3 we give a
reduction from k-SAT to CVP∞ and SVP∞ , proving the special case of Theorem 1.1 for p = ∞.
Our reductions all use the same high-level idea as the reduction given in Theorem 3.2, but each
uses new ideas as well. Throughout this section we adopt the notation from Section 3.

6.1

Hardness of CVPPp

In this section, we prove ETH-hardness of CVPP. To do this, for every n, we construct a single
lattice Ln ⊂ Rd of rank O(n2 ), such that for every n-variable instance of Max-2-SAT, there exists
an efficiently computable t ∈ Rd that is close to the lattice if and only if Φ is satisfiable. Clearly,
any efficient algorithm for CVPP on this lattice would imply a similarly efficient algorithm for
Max-2-SAT (and also 3-SAT, as described below).
Our basis Bn for Ln will encode all possible O(n2 ) clauses of a Max-2-SAT instance on n
variables, together with a gadget that will allow us to “switch on or off” each clause by only changing
the coordinates of the target vector t. (This gadget costs us a quadratic blow-up in the lattice rank.)
Then, given an instance (Φ, W ) of Max-2-SAT, we define the target vector t such that it “switches
on” all clauses from Φ and “switches off” all the remaining clauses.
Lemma 6.1. For every p ∈ [1, ∞), there is a pair of polynomial-time algorithms (P, Q) (in analogy
to the definition of CVPP) that behave as follows.
1. On input an integer n ≥ 1, P outputs a basis Bn ∈ Rd×N of a rank N lattice Ln ⊂ Rd , where
d = d(n) = O(n2 ) and N = N (n) = O(n2 ).
2. On input a Max-2-SAT instance with n variables, Q outputs a target vector t ∈ Rd and a
distance bound r ≥ 0 such that distp (t, Ln ) ≤ r if and only if the input is a ‘YES’ instance.
Proof. Let M = 4 n2 = O(n2 ) be the total possible number of 2-clauses on n variables, and let
C1 , . . . , CM denote those clauses.
The algorithm P constructs the basis Bn ∈ Rd×N , where d := n + 2M, N := n + M , as


(bT1 , cT1 )


..


.




B := 


,

(bTM , cTM )

2α1/p IN

with rows (bTi , cTi ) of B satisfying bi ∈ Rn and ci ∈ RM for 1 ≤ i ≤ M , and where α := 2p M .
For every 1 ≤ i ≤ M and 1 ≤ j ≤ n, set the jth coordinate of bi (corresponding to the clause
Ci = `i,1 ∨ `i,2 ) as
26

(bi )j :=





1 if xj appears in the ith clause,
−1 if ¬xj appears in the ith clause,

 0 otherwise.

For every 1 ≤ i ≤ M , set cTi := (0T(i−1) , 1, 0T(M −i) ), i.e., set (c1 , . . . , cM ) = IM .
Given an instance (Φ, W ) of Max-2-SAT with m clauses, the algorithm Q outputs
r := (M − m + W ) · 1/2p + (m − W ) · (3/2)p + α(n + M − m)
and t ∈ Rd defined as

u1
..
.



1/p







uM


t :=  α1/p · 1n


v1


..

.







,






vM
where for 1 ≤ i ≤ M , ui = 3/2 − |Ni |, and vi = 0 if the clause Ci appears in the formula Φ and
vi = α1/p otherwise.
Clearly both algorithms are efficient. We now analyze for which y ∈ ZN we have kBy − tkp ≤ r.
Note that the vector v = (v1 , . . . , vM )T has exactly m coordinates equal to zero, and M − m
coordinates equal to α1/p . Given y ∈
/ {0, 1}N , we have
kBy − tkpp ≥ k2α1/p IN y − (α1/p 1Tn , v T )T kpp ≥ α(n + M − m + 1) ≥ 2p M + α(M + n − m) > rp .
Furthermore, if y ∈ {0, 1}N has a non-zero coordinate yn+M +i (for 1 ≤ i ≤ M ) at a position
corresponding to a tn+M +i = 0 in t (i.e., Ci ∈ Φ), then again kBy − tkpp ≥ α(n + M − m + 1) > rp .
So, we can restrict our attention to y ∈ {0, 1}N with yn+M +i = 0 whenever Ci ∈ Φ.
0 )T ∈ {0, 1}M ,
Consider an assignment a ∈ {0, 1}n to the n variables of Φ. Take (y 0 )T = (y10 , . . . yM
T
0
T
T
and set y := (a , (y ) ) . Then, for 1 ≤ i ≤ M ,
h(bTi , cTi )T , yi − ti =

X

yind(`i,s ) −

s∈Pi

=

X
s∈Pi

X

yind(`i,s ) + hci , y 0 i − (3/2 − |Ni |)

s∈Ni

yind(`i,s ) −

X

(1 − yind(`i,s ) ) + yi0 − 3/2

s∈Ni

= |Si (a)| + yi0 − 3/2 .
If Ci ∈
/ Φ, then there exists yi0 ∈ {0, 1}, such that |h(bTi , cTi )T , yi − ti | = 1/2. Moreover, the choice
0
of yi does not affect |h(bTi , cTi )T , yi − ti0 | for i0 6= i. If Ci ∈ Φ and |Si (a)| > 0 for yi0 = 0, then
|h(bTi , cTi )T , yi − ti | = 1/2. On the other hand, if Ci ∈ Φ and |Si (a)| = 0, then yi0 = 0 implies
|h(bTi , cTi )T , yi − ti | ≥ 3/2.
Because |Si (a)| ≥ 1 if and only if Ci is satisfied, we see that the following holds if and only if
the number of satisfied clauses m+ (a) is at least W :

27

There exists a y 0 such that, setting y := (a, y 0 ), we have
kBy −

tkpp

=

M
X



|h(bTi , cTi )T , yi − ti |p + α(n + M − m)

i=1

= (M − m + m+ (a)) · (1/2)p + (m − m+ (a)) · (3/2)p + α(n + M − m)
≤ (M − m + W ) · (1/2)p + (m − W ) · (3/2)p + α(n + M − m)
= rp .
Therefore, there exists y with kBy − tkp ≤ r if and only if (Φ, W ) is a ‘YES’ instance of
Max-2-SAT.
Proof of Theorem 1.4. The main statement follows from Lemma 6.1. The “in particular” part
follows from Lemma 6.1 and the existence of a reduction from 3-SAT with n variables clauses to
(many) Max-2-SAT instances with O(n) variables. Indeed, such a reduction follows by applying
the Sparsification Lemma (Proposition 2.9), and then reducing each sparse 3-SAT instance to a
Max-2-SAT instance with only a linear blow-up in the number of variables (see, e.g., the reduction
in [GJS76, Theorem 1.1]).

6.2

ETH- and Max-2-SAT-hardness for all p ∈ [1, ∞)

Theorem 6.2. For every p = p(n) ∈ [1, ∞) and k ≥ 2 there is a polynomial-time reduction from
any (Weighted-)Max-k-SAT instance with n variables and m clauses to a CVPp instance of rank
n + (k − 2)m.
Proof. For simplicity we give a reduction from unweighted Max-k-SAT. The modification sketched
for reducing from Weighted Max-k-SAT in Theorem 3.2 works here as well. Namely, we give a
reduction from a Max-k-SAT instance (Φ, W ) to an instance (B, t, r) of CVPp . Here the formula Φ
is on n variables x1 , . . . , xn and m clauses C1 , . . . , Cm . (Φ, W ) is a ‘YES’ instance if there exists an
assignment a such that m+ ≥ W . We assume without loss of generality that each variable appears
at most once per clause. We define the output CVPp instance as follows. Let d := n + (k − 1)m
and let N := n + (k − 2)m. The basis B ∈ Rd×N in the output instance has the form
(bT1 , cT1 )


..


.







B=
 T T ,
 (bm , cm ) 

2α1/p · IN



t=



t1
..
.

tm
α1/p · 1N








with rows (bTi , cTi ) of B satisfying bi ∈ Rn and ci ∈ Rm(k−2) for 1 ≤ i ≤ m, and where α :=
W · ( 12 )p + (m − W ) · ( 32 )p . For every 1 ≤ i ≤ m and 1 ≤ j ≤ n, set the jth coordinate of bi
(corresponding to the clause Ci = ∨ks=1 `i,s ) as




1 if xj is in the ith clause,
−1 if ¬xj is in the ith clause,
(bi )j :=

 0 otherwise.
For every 1 ≤ i ≤ m, set cTi := (0T(i−1)(k−2) , −1Tk−2 , 0T(m−i)(k−2) ). I.e., each ci has a block of −1s of
length k−2, and ci , ci0 are coordinate-wise disjoint for i 6= i0 . For every 1 ≤ i ≤ m set ti := 3/2−|Ni |.
Finally, set r := (α(N + 1))1/p .
28

We next analyze for which y ∈ ZN it holds that kBy − tkp ≤ r. Given y ∈
/ {0, 1}N , kBy − tkpp ≥
k2α1/p IN y − α1/p 1N kpp ≥ α(N + 2) > rp , so we only need to analyze the case when y ∈ {0, 1}n .
Consider an assignment a ∈ {0, 1}n to the variables of Φ, take (y 0 )T = ((y 01 )T , . . . , (y 0m )T ) ∈
{0, 1}(k−2)m with y 0i ∈ {0, 1}k−2 for 1 ≤ i ≤ m, and set y T := (aT , (y 0 )T ). Then, for 1 ≤ i ≤ m,
h(bTi , cTi )T , yi − ti =

X

yind(`i,s ) −

s∈Pi

=

X

X

yind(`i,s ) + hci , y 0i i − (3/2 − |Ni |)

s∈Ni

yind(`i,s ) +

s∈Pi

= |Si (a)| −

X

(1 − yind(`i,s ) ) − ky 0i k1 − 3/2

s∈Ni

ky 0i k1

− 3/2 .

It follows that if |Si (a)| = 0 then |h(bTi , cTi )T , yi − ti | ≥ 32 . On the other hand, if |Si (a)| ≥ 1,
then there exists y 0i ∈ {0, 1}k−2 such that |h(bTi , cTi )T , yi − ti | = 12 . Indeed, picking any y 0i with
Hamming weight |Si (a)| − 2 or |Si (a)| − 1 achieves this. Moreover, the choice of y 0i does not affect
|h(bTi , cTi )T , yi − ti0 | for i0 6= i.
Because |Si (a)| ≥ 1 if and only if Ci is satisfied, we see that the following holds if and only if
the number of satisfied clauses m+ (a) is at least W :
There exists a y 0 such that, setting y := (a, y 0 ), we have
kBy − tkpp =

m
X



|h(bTi , cTi )T , yi − ti |p + αN

i=1
+

= m (a) · (1/2)p + (m − m+ (a)) · (3/2)p + αN
≤ W · (1/2)p + (m − W ) · (3/2)p + αN
= rp .
Therefore, there exists y such that kBy − tkp ≤ r if and only if (Φ, W ) is a ‘YES’ instance of
Max-k-SAT.
We remark that a straightforward modification of the preceding reduction gives a reduction from
an instance of Max-k-SAT with k ≥ 3 on n variables and m clauses to a CVPp instance of rank
n + (blog2 (k − 2)c + 1)m (as opposed to rank n + (k − 2)m). The idea is to encode the value k − 2
(corresponding to the row-specific blocks −1k−2 used in the reduction) in binary rather than unary.
Corollary 6.3. For every p ∈ [1, ∞) there is no 2o(n) -time algorithm for CVPp assuming ETH.
Proof. The claim follows by combining the Sparsification Lemma (Proposition 2.9) with the reduction
in Theorem 6.2.10
When k = 2, the rank of the CVPp instance output by the reduction in Theorem 6.2 is n.
Therefore, we get the following corollary.
Corollary 6.4. If there exists a 2(ω/3−ε)n -time (resp. 2(1−ε)n -time and polynomial space) algorithm
for CVPp for any p ∈ [1, ∞) and for any constant ε > 0, then there exists a 2(ω/3−ε)n -time (resp.
2(1−ε)n -time and polynomial space) algorithm for (Weighted-)Max-2-SAT and (Weighted-)Max-Cut.
10

As a technical point, we must reduce from k-SAT rather than Max-k-SAT to show hardness under ETH because
the Sparsification Lemma works for k-SAT.

29

6.3

The hardness of SVP∞ and CVP∞

Theorem 6.5. There is a polynomial-time reduction from a k-SAT instance with n variables to a
CVP∞ instance of rank n.
Proof. We give a reduction from a k-SAT formula Φ with n variables x1 , . . . , xn and m clauses
C1 , . . . , Cm to an instance (B, t, r) of CVP∞ . We assume without loss of generality that each
variable appears at most once per clause. We define the output CVP∞ instance as follows. Let
d := m + n. The basis B ∈ Rd×n in the output instance has the form
bT1
..
.





B=





bTm
(k + 1) · In



t1
..
.






,



t=



tm
(k + 1)/2 · 1n




,



with rows bi of B satisfying bi ∈ Rn for 1 ≤ i ≤ m. For every 1 ≤ i ≤ m, set bi as in the proof of
Theorem 6.2 and set ti := (k + 1)/2 − |Ni |. Set r := (k − 1)/2.
We next analyze for which y ∈ Zn it holds that kBy − tk∞ ≤ r. Given y ∈
/ {0, 1}n , kBy − tk∞ ≥
k(k − 1) · In y − (k − 1)/2 · 1n k∞ ≥ 3(k − 1)/2 > r, so we only need to analyze the case when
y ∈ {0, 1}n . Consider an assignment y ∈ {0, 1}n to the variables of Φ. Then
hbi , yi − ti =

X

yind(`i,s ) −

s∈Pi

=

X

X

yind(`i,s ) − ((k + 1)/2 − |Ni |)

s∈Ni

yind(`i,s ) −

s∈Pi

X

(1 − yind(`i,s ) ) − (k + 1)/2

s∈Ni

= |Si (a)| − (k + 1)/2 .
It follows that if |Si (a)| = 0 then |hbi , yi − ti | = (k + 1)/2, and otherwise |hbi , yi − ti | ≤ (k − 1)/2.
Because |Si (a)| ≥ 1 if and only if Ci is satisfied, we then have that kBy − tk∞ = max{|hb1 , yi −
t1 |, . . . , |hbm , yi − tm |, (k − 1)/2} = (k − 1)/2 = r if y satisfies Φ, and kBy − tk∞ = (k + 1)/2 > r
otherwise. Therefore there exists y such that kBy − tk∞ ≤ r if and only if Φ is satisfiable.
Lemma 6.6. There is a polynomial-time reduction from a k-SAT instance with n variables to an
SVP∞ instance of rank n + 1.
Proof. We give a reduction from a k-SAT formula Φ with n variables x1 , . . . , xn and m clauses
C1 , . . . , Cm to an instance (B 0 , r) of SVP∞ . Define the basis B 0 ∈ R(m+n+1)×(n+1) as
0

B :=

B
0Tn

!

−t
,
−(k − 1)/2

where B and t are as defined in the proof of Theorem 6.5, and set r := (k − 1)/2. We consider for
which y ∈ Zn+1 \ {0n+1 } it holds that kByk∞ ≤ r. It is not hard to check that if |yi | ≥ 2 for some
1 ≤ i ≤ n + 1, or if the signs of yi and yn+1 differ for some 1 ≤ i ≤ n, then kByk∞ > r. Therefore
we need only consider y of the form y = ±(aT , 1)T where a ∈ {0, 1}n . But for such a y we have
that kB 0 yk∞ = kBa − tk∞ , and kBa − tk∞ ≤ (k − 1)/2 if and only if a is a satisfying assignment
to Φ by the analysis in the proof of Theorem 6.5.
30

Corollary 6.7. For any constant ε > 0 there is no 2(1−ε)n -time algorithm for SVP∞ or CVP∞
assuming SETH, and there is no 2o(n) -time algorithm for SVP∞ or CVP∞ assuming ETH.
Proof. Combine Theorem 6.5 and Lemma 6.6.
Note that the preceding reduction in fact achieves an approximation factor of γ = γ(k) :=
1 + 2/(k − 1). This implies that for every constant ε > 0, there is a γε > 1 such that no 2(1−ε)n -time
algorithm that approximates SVP∞ or CVP∞ to within a factor of γε unless SETH fails.
Finally, we remark that the reduction given in Theorem 6.2 is parsimonious when used as a
reduction from 2-SAT. I.e., there is a one-to-one correspondence between satisfying assignments in
the input instance and close vectors in the output instance. The reductions given in Theorem 6.5
and Lemma 6.6 are also parsimonious.11
Because #2-SAT is #P-hard, our reductions therefore show that the counting version of CVPp
(called the Vector Counting Problem) is #P-hard for all 1 ≤ p ≤ ∞, and that the counting version of
SVP∞ is #P-hard. This improves (and arguably simplifies the proof of) a result of Charles [Cha07],
which showed that the counting version of CVP2 is #P-hard.

Acknowledgments
We would like to thank Oded Regev for many fruitful discussions and for helpful comments on an
earlier draft of this work. We also thank Vinod Vaikuntanathan for recommending that we consider
Gap-ETH.

References
[ABSS93] Sanjeev Arora, László Babai, Jacques Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. In FOCS, 1993.
[ABW15]

Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness
results for LCS and other sequence similarity measures. In FOCS, 2015.

[ADPS16] Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe. Post-quantum key
exchange — A new hope. In USENIX Security Symposium, 2016.
[ADRS15] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving
the Shortest Vector Problem in 2n time via discrete Gaussian sampling. In STOC, 2015.
[ADS15]

Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz. Solving the Closest
Vector Problem in 2n time— The discrete Gaussian strikes again! In FOCS, 2015.

[AJ08]

V. Arvind and Pushkar S. Joglekar. Some sieving algorithms for lattice problems. In
IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science, 2008.

[Ajt98]

Miklós Ajtai. The Shortest Vector Problem in L2 is NP-hard for randomized reductions.
In STOC, 1998.

11
Actually, in the case of SVP∞ , each satisfying assignment to the SAT formula corresponds to a pair ±v of shortest
non-zero vectors, so that there are exactly twice as many such vectors as there are satisfying assignments.

31

[Ajt04]

Miklós Ajtai. Generating hard instances of lattice problems. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 1–32. Dept. Math., Seconda Univ.
Napoli, Caserta, 2004. Preliminary version in STOC’96.

[AKKV11] Mikhail Alekhnovich, Subhash Khot, Guy Kindler, and Nisheeth K. Vishnoi. Hardness
of approximating the Closest Vector Problem with Pre-processing. Computational
Complexity, 20, 2011.
[AKS01]

Miklós Ajtai, Ravi Kumar, and D. Sivakumar. A sieve algorithm for the Shortest Lattice
Vector Problem. In STOC, 2001.

[AKS02]

Miklós Ajtai, Ravi Kumar, and D. Sivakumar. Sampling short lattice vectors and the
Closest Lattice Vector Problem. In CCC, 2002.

[APS15]

Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning
with Errors. J. Mathematical Cryptology, 9(3):169–203, 2015.

[AR05]

Dorit Aharonov and Oded Regev. Lattice problems in NP ∩ coNP. J. ACM, 52(5):749–
765, 2005. Preliminary version in FOCS 2004.

[BCD+ 16] Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria
Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the ring!
Practical, quantum-secure key exchange from LWE. In CCS, 2016.
[BD15]

Nicolas Bonifas and Daniel Dadush. Short paths on the Voronoi graph and the Closest
Vector Problem with Preprocessing. In SODA, 2015.

[BDGL16] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest
neighbor searching with applications to lattice sieving. In SODA, 2016.
[BI15]

Arturs Backurs and Piotr Indyk. Edit Distance cannot be computed in strongly
subquadratic time (unless SETH is false). In STOC, 2015.

[BN09]

Johannes Blömer and Stefanie Naewe. Sampling methods for shortest vectors, closest
vectors and successive minima. Theoret. Comput. Sci., 410(18):1648–1665, 2009.

[CDL+ 12] Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio
Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems
as hard as CNF-SAT. In CCC, 2012.
[CFK+ 15] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx,
Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms.
Springer, 2015.
[Cha07]

Denis Xavier Charles. Counting lattice vectors. J. Comput. Syst. Sci., 73(6):962–972,
2007.

[CLR+ 14] Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre
Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the
graph diameter. In SODA, 2014.

32

[CN98]

Jin-Yi Cai and Ajay Nerurkar. Approximating the SVP to within a factor (1 + 1/ dimε )
is NP-hard under randomized conditions. In CCC, 1998.

[Dad12]

Daniel Dadush. A O(1/ε2 )n -time sieving algorithm for approximate Integer Programming.
In LATIN, 2012.

[Din16]

Irit Dinur. Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover.
Electronic Colloquium on Computational Complexity (ECCC), 23:128, 2016.

[DKRS03] Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within
almost-polynomial factors is NP-hard. Combinatorica, 23(2):205–243, 2003.
[DPV11]

Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in
any norm via M-ellipsoid coverings. In FOCS, 2011.

[DRS14]

Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. On the Closest Vector
Problem with a distance guarantee. In CCC, pages 98–109, 2014.

[FM04]

Uriel Feige and Daniele Micciancio. The inapproximability of lattice and coding problems
with preprocessing. Journal of Computer and System Sciences, 69(1):45–67, 2004.
Preliminary version in CCC 2002.

[GG00]

Oded Goldreich and Shafi Goldwasser. On the limits of nonapproximability of lattice
problems. J. Comput. Syst. Sci., 60(3):540–563, 2000. Preliminary version in STOC
1998.

[GHNR03] Jens Gramm, Edward A. Hirsch, Rolf Niedermeier, and Peter Rossmanith. Worst-case
upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied
Mathematics, 130(2):139–155, 2003.
[GJS76]

Michael R. Garey, David S. Johnson, and Larry Stockmeyer. Some simplified NPcomplete graph problems. Theoretical Computer Science, 1(3):237–267, 1976.

[GMSS99] Oded Goldreich, Daniele Micciancio, Shmuel Safra, and Jean-Pierre Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.
Information Processing Letters, 71(2):55 – 61, 1999.
[GN08]

Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell’s
inequality. In STOC, 2008.

[GPV08]

Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices
and new cryptographic constructions. In STOC, pages 197–206, 2008.

[HP]

S. Har-Peled. Concentration of Random Variables – Chernoff’s Inequality. Available at
http://sarielhp.org/teach/13/b_574_rand_alg/lec/07_chernoff.pdf.

[HR12]

Ishay Haviv and Oded Regev. Tensor-based hardness of the Shortest Vector Problem to
within almost polynomial factors. Theory of Computing, 8(23):513–531, 2012. Preliminary
version in STOC’07.

33

[IP99]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. In CCC,
pages 237–240, 1999.

[IPZ01]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have
strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512–530, 2001.

[Jam06]

G. J. O. Jameson. Counting zeros of generalised polynomials: Descartes’ rule of signs
and Laguerre’s extensions. The Mathematical Gazette, 90(518):223–234, 2006.

[JS98]

Antoine Joux and Jacques Stern. Lattice reduction: A toolbox for the cryptanalyst.
Journal of Cryptology, 11(3):161–185, 1998.

[Kan87]

Ravi Kannan. Minkowski’s convex body theorem and Integer Programming. Math. Oper.
Res., 12(3):415–440, 1987.

[Kho05]

Subhash Khot. Hardness of approximating the Shortest Vector Problem in lattices.
Journal of the ACM, 52(5):789–808, September 2005. Preliminary version in FOCS’04.

[KPV14]

Subhash Khot, Preyas Popat, and Nisheeth K. Vishnoi. 2log n hardness for Closest
Vector Problem with Preprocessing. SIAM Journal on Computing, 43(3):1184–1205,
2014.

[Laa15]

Thijs Laarhoven. Sieving for shortest vectors in lattices using angular locality-sensitive
hashing. In CRYPTO, 2015.

[Len83]

Hendrik W. Lenstra, Jr. Integer Programming with a fixed number of variables. Math.
Oper. Res., 8(4):538–548, 1983.

[LG14]

François Le Gall. Powers of tensors and fast matrix multiplication. In ISAAC, 2014.

[LLL82]

Arjen K. Lenstra, Hendrik W. Lenstra, Jr., and László Lovász. Factoring polynomials
with rational coefficients. Math. Ann., 261(4):515–534, 1982.

1−ε

[LWXZ11] Mingjie Liu, Xiaoyun Wang, Guangwu Xu, and Xuexin Zheng. Shortest lattice vectors
in the presence of gaps. IACR Cryptology ePrint Archive, 2011:139, 2011.
[Mic01a]

Daniele Micciancio. The hardness of the Closest Vector Problem with Preprocessing.
IEEE Transactions on Information Theory, 47(3):1212–1215, 2001.

[Mic01b]

Daniele Micciancio. The Shortest Vector Problem is NP-hard to approximate to within
some constant. SIAM Journal on Computing, 30(6):2008–2035, March 2001. Preliminary
version in FOCS 1998.

[MR17]

Pasin Manurangsi and Prasad Raghavendra. A birthday repetition theorem and complexity of approximating dense csps. In 44th International Colloquium on Automata,
Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages
78:1–78:15, 2017.

[MV10]

Daniele Micciancio and Panagiotis Voulgaris. Faster exponential time algorithms for the
Shortest Vector Problem. In SODA, pages 1468–1480, 2010.

34

[MV13]

Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time
algorithm for most lattice problems based on Voronoi cell computations. SIAM Journal
on Computing, 42(3):1364–1391, 2013.

[MW15]

Daniele Micciancio and Michael Walter. Fast lattice point enumeration with minimal
overhead. In SODA, 2015.

[MW16]

Daniele Micciancio and Michael Walter. Practical, predictable lattice basis reduction.
In Eurocrypt, 2016.

[NIS16]

NIST post-quantum standardization call for proposals. http://csrc.nist.gov/
groups/ST/post-quantum-crypto/cfp-announce-dec2016.html, 2016. Accessed:
2017-04-02.

[NS01]

Phong Q. Nguyen and Jacques Stern. The two faces of lattices in cryptology. In
Cryptography and Lattices, pages 146–180. Springer, 2001.

[NV08]

Phong Q. Nguyen and Thomas Vidick. Sieve algorithms for the shortest vector problem
are practical. J. Math. Cryptol., 2(2):181–207, 2008.

[Odl90]

Andrew M. Odlyzko. The rise and fall of knapsack cryptosystems. Cryptology and
Computational Number Theory, 42:75–88, 1990.

[Pei08]

Chris Peikert. Limits on the hardness of lattice problems in `p norms. Computational
Complexity, 17(2):300–351, May 2008. Preliminary version in CCC 2007.

[Pei16]

Chris Peikert. A decade of lattice cryptography. Foundations and Trends in Theoretical
Computer Science, 10(4):283–424, 2016.

[PS09]

Xavier Pujol and Damien Stehlé. Solving the Shortest Lattice Vector Problem in time
22.465n . IACR Cryptology ePrint Archive, 2009:605, 2009.

[PW10]

Mihai Pătraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In
SODA, 2010.

[Reg04]

Oded Regev. Improved inapproximability of lattice and coding problems with preprocessing. IEEE Transactions on Information Theory, 50(9):2031–2037, 2004. Preliminary
version in CCC’03.

[Reg09]

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography.
Journal of the ACM, 56(6):Art. 34, 40, 2009.

[RR06]

Oded Regev and Ricky Rosen. Lattice problems and norm embeddings. In STOC, 2006.

[Sch87]

Claus P. Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms.
Theoretical Computer Science, 53:201 – 224, 1987.

[SFS09]

Naftali Sommer, Meir Feder, and Ofir Shalvi. Finding the closest lattice point by
iterative slicing. SIAM J. Discrete Math., 23(2):715–731, 2009.

[Sha84]

Adi Shamir. A polynomial-time algorithm for breaking the basic Merkle-Hellman
cryptosystem. IEEE Trans. Inform. Theory, 30(5):699–704, 1984.
35

[Vai15]

Vinod Vaikuntanathan. Private communication, 2015.

[vEB81]

Peter van Emde Boas. Another NP-complete problem and the complexity of computing
short vectors in a lattice. Technical report, University of Amsterdam, Department of
Mathematics, Netherlands, 1981. Technical Report 8104.

[Wil05]

Ryan Williams. A new algorithm for optimal 2-Constraint Satisfaction and its implications. Theoretical Computer Science, 348(2-3):357–365, 2005.

[Wil12]

Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd.
In STOC, 2012.

[Wil15]

Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular
conjectures such as the Strong Exponential Time Hypothesis (invited talk). In IPEC,
pages 17–29, 2015.

[Wil16]

Ryan Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive
proofs of batch evaluation. In CCC, 2016.

[WLTB11] Xiaoyun Wang, Mingjie Liu, Chengliang Tian, and Jingguo Bi. Improved Nguyen-Vidick
heuristic sieve algorithm for shortest vector problem. In ASIACCS, 2011.
[Woe08]

Gerhard J. Woeginger. Open problems around exact algorithms. Discrete Applied
Mathematics, 156(3):397–405, 2008.

36

