Pages that link to "Item:Q1961373"
From MaRDI portal
The following pages link to Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions (Q1961373):
Displaying 14 items.
- Lower bounds of shortest vector lengths in random NTRU lattices (Q477183) (← links)
- A note on the non-NP-hardness of approximate lattice problems under general Cook reductions. (Q1589481) (← links)
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard (Q1608337) (← links)
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor (Q1861566) (← links)
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms (Q2490259) (← links)
- A note on the concrete hardness of the shortest independent vector in lattices (Q2656338) (← links)
- The shortest vector in a lattice is hard to approximate to within some constant (Q2719121) (← links)
- Inapproximability of the shortest vector problem: toward a deterministic reduction (Q2913823) (← links)
- Tensor-based hardness of the shortest vector problem to within almost polynomial factors (Q2913824) (← links)
- The Geometry of Lattice Cryptography (Q3092183) (← links)
- Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One (Q4636451) (← links)
- Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH (Q5002683) (← links)
- A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem (Q5892608) (← links)
- On the unique shortest lattice vector problem (Q5941093) (← links)
