A polynomial time algorithm for GapCVPP in l₁ norm

DOI10.1007/S11432-013-4795-8zbMATH Open1343.68101OpenAlexW1996002292MaRDI QIDQ893692FDOQ893692

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

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

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)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Factoring polynomials with rational coefficients
• Title not available (Why is that?)
• Lattice problems and norm embeddings
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Approximating CVP to within almost-polynomial factors is NP-hard
• Inequalities for convex bodies and polar reciprocal lattices in \(\mathbb{R}^ n\)
• Lattice problems in NP ∩ coNP
• Limits on the hardness of lattice problems in \(\ell_{p}\) norms
• The inapproximability of lattice and coding problems with preprocessing
• Improved Inapproximability of Lattice and Coding Problems With Preprocessing
• The hardness of the closest vector problem with preprocessing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard

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)