A polynomial time algorithm for GapCVPP in l₁ norm

DOI10.1007/S11432-013-4795-8MaRDI QIDQ893692zbMATH OpenOpenAlexFDO

Authors Chengliang Tian, Lidong Han, 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

computational complexitylatticesalgorithmclosest vector problem with preprocessingLaplace measures

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Lattices and convex bodies (number-theoretic aspects) (11H06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• The inapproximability of lattice and coding problems with preprocessing
• The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm
• Approximate CVP\(_p\) in time \(2^{0.802n}\)
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• Almost polynomial factor hardness for closest vector problem with preprocessing

Cites work

• scientific article; zbMATH DE number 4213909 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 2088306 (Why is no real title available?)
• Approximating CVP to within almost-polynomial factors is NP-hard
• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
• Factoring polynomials with rational coefficients
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Lattice problems and norm embeddings
• Lattice problems in NP ∩ coNP
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• Probability Inequalities for Sums of Bounded Random Variables
• The hardness of the closest vector problem with preprocessing
• The inapproximability of lattice and coding problems with preprocessing
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q893692)