A polynomial time algorithm for GapCVPP in \(l_1\) norm
From MaRDI portal
Publication:893692
DOI10.1007/s11432-013-4795-8zbMath1343.68101OpenAlexW1996002292MaRDI QIDQ893692
Lidong Han, Chengliang Tian, Guangwu Xu
Publication date: 20 November 2015
Published in: Science China. Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11432-013-4795-8
Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Lattices and convex bodies (number-theoretic aspects) (11H06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Limits on the hardness of lattice problems in \(\ell_{p}\) norms
- Factoring polynomials with rational coefficients
- Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
- Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
- Approximating CVP to within almost-polynomial factors is NP-hard
- The inapproximability of lattice and coding problems with preprocessing
- Lattice problems and norm embeddings
- Lattice problems in NP ∩ coNP
- Improved Inapproximability of Lattice and Coding Problems With Preprocessing
- The hardness of the closest vector problem with preprocessing
- Probability Inequalities for Sums of Bounded Random Variables
- Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
