A polynomial time algorithm for GapCVPP in \(l_1\) norm

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

zbMATH Keywords

algorithmcomputational complexitylatticesclosest vector problem with preprocessingLaplace measures

Mathematics Subject Classification ID

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

This page was built for publication: A polynomial time algorithm for GapCVPP in \(l_1\) norm