Pages that link to "Item:Q1878613"
From MaRDI portal
The following pages link to Approximating CVP to within almost-polynomial factors is NP-hard (Q1878613):
Displayed 35 items.
- Matrix sparsification and the sparse null space problem (Q329287) (← links)
- Hardness of approximating the closest vector problem with pre-processing (Q430834) (← links)
- An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm (Q498420) (← links)
- Voronoi polytopes for polyhedral norms on lattices (Q499359) (← links)
- An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\) (Q845926) (← links)
- A polynomial time algorithm for GapCVPP in \(l_1\) norm (Q893692) (← links)
- An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)) (Q924126) (← links)
- Sampling methods for shortest vectors, closest vectors and successive minima (Q1014636) (← links)
- Hardness of approximating the minimum solutions of linear Diophantine equations (Q1022600) (← 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 semidefinite programming method for integer convex quadratic minimization (Q1749779) (← links)
- A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor (Q1861566) (← links)
- The inapproximability of lattice and coding problems with preprocessing (Q1881262) (← links)
- Approximate CVP\(_p\) in time \(2^{0.802n}\) (Q2051858) (← links)
- Covering convex bodies and the closest vector problem (Q2136842) (← links)
- Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! (Q2164729) (← links)
- Ciphertext-only attacks against compact-LWE submitted to NIST PQC project (Q2165453) (← links)
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems (Q2237900) (← links)
- Restricted parameter range promise set cover problems are easy (Q2258109) (← links)
- The remote set problem on lattices (Q2353188) (← links)
- Approximating multidimensional subset sum and Minkowski decomposition of polygons (Q2364904) (← links)
- On the complexity of quasiconvex integer minimization problem (Q2423784) (← links)
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms (Q2490259) (← links)
- Complexity and algorithms for computing Voronoi cells of lattices (Q3055167) (← links)
- Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle (Q3088093) (← links)
- The Geometry of Lattice Cryptography (Q3092183) (← links)
- Voronoi Cells of Lattices with Respect to Arbitrary Norms (Q3174772) (← links)
- NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem (Q4581908) (← links)
- Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH (Q5002683) (← links)
- A Polynomial Time Algorithm for Solving the Closest Vector Problem in Zonotopal Lattices (Q5163506) (← links)
- Just Take the Average! An Embarrassingly Simple $2^n$-Time Algorithm for SVP (and CVP) (Q5240427) (← links)
- A Digital Signature Scheme Based on CVP ∞ (Q5445459) (← links)
- Approximate CVP_p in Time 2^{0.802 n} (Q5874513) (← links)
- Improvements in the analysis of Kannan's CVP algorithm (Q5964026) (← links)